본문 바로가기

알고리즘35

백준 16137/SWEA 4727 견우와 직녀 건널 수 있는지 여부 확인 방법 쉬는 시간엔 건널 수 없다! 대기하는 걸 구현하지 않고 이미 대기한 후의 시간(nt)을 계산해서 큐에 넣는다 int waitTime = map[nx][ny] 또는 m (원래 오작교인지 새로 짓는 오작교인지 여부에 따라) int nt = t + (waitTime - (t%waitTime); BFS 건널 수 있는 경우(길, 오작교)와 없는 경우(절벽)으로 나눈다 건널 수 있는 경우 길 ⇒ 일반 BFS 오작교 : 이전에 건넌 적 없었는지 확인 없는 경우 : 새로운 오작교를 만들 수 있는가를 확인! 직전 칸(map[x][y])이 오작교였던 경우 불가 교차하는 곳은 불가 : 포문 돌리며 가로와 세로에 있는 1의 개수를 세어 둘 다 1 이상이면 불가 BFS 코드 static void.. 2020. 5. 16.
카카오 코딩테스트 2019 블록 게임 종류 : 브루트포스 1. 사실 없앨 수 있는 블록의 모양은 다섯개 뿐이다 - 검은 돌을 떨어트려서 꽉 찬 모양을 만들려면 동그라미 친 다섯 개 모양 중 하나여야 한다 2. 기준점을 (0, 0) 잡고 블록의 다른 부분을 상대좌표로 표현해준다 => types에 미리 저장 - 채워야 할 부분은 empty에 상대좌표로 미리 저장해 놓는다 types = [ # 각 행은 모양의 인덱스 [[1, 0], [1, 1], [1, 2]], [[1,0],[2,0],[2,-1]], [[1,0],[2,0],[2,1]], [[1,0],[1,-1],[1,-2]], [[1,0],[1, -1], [1, 1]] ] empty=[ [[0, 1], [0, 2]], [[0, -1], [1, -1]], [[0, 1], [1, 1]], [[0, .. 2020. 5. 5.
SWEA 5653 줄기세포 배양 풀이방식 Priority Queue를 활용한 시뮬레이션 baby : 비활성화 세포 (활성화 시간 기준 PQ) adult : 번식할 세포 (생명력 기준 PQ) old : 활성화됐지만 번식하지 않는 세포 (죽는 시간 기준 PQ) 활성화되는 시간 : 태어난 시간(birth) + 생명력(power) 죽는 시간 : 태어난 시간(birth) + (생명력(power) * 2) 1. 번식 adult 큐에서 상하좌우 탐색 - 비어있으면 채우기 - adult에 넣기 2. 활성 baby 큐에서 (활성화시간 == 현시간)인 애들를 adult에 옮기기 (우선순위 큐이므로 안 되는 애가 나오면 바로 break : 그 뒤로는 이후에 활성화되는 애들이기 때문) 3. 죽은 세포 처리 : old 큐에서 (죽는 시간==현시간)인 애들을 .. 2020. 4. 24.
백준 게리맨더링 2 풀이 경계선의 안쪽 부분을 어떻게 처리해줄지가 가장 어려웠다. (x, y)를 마름모꼴의 윗 꼭짓점이라고 했을 때, x부터 x+d1+d2까지 포문을 돌리며 5에서 5사이를 처리해준다 즉, 마름모꼴의 맨 위부터 맨 밑까지 경계선이 5로 칠해져있기 때문에 5 0 0 0 0 5 이 부분을 5 5 5 5 5 5 이렇게 바꿔서 선거구 5로 기록해준다 (오답부분 그림 참고) import java.io.BufferedReader; import java.io.FileInputStream; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public cla.. 2020. 4. 24.