presentLee

https://www.acmicpc.net/problem/2573 한덩어리로 뭉쳐져있는(dfs로 한번에 탐색 가능한) 빙산이 입력되고, 그것이 두덩이 이상으로 쪼개질 때를 감지해야한다. 풀이1내가 푼 방식입력받으면서 빙하인 부분을 큐에 담는다.1년 진행마다 기존 빙하와 바다 상태(arr)의 정보를 복사한다(copied)큐에서 poll하며 빙하가 있던 곳의 위치를 기반으로 copied에 있는 빙하를 녹인다.(복사해서 하는 이유는, 원래 arr에서 순차적으로 녹일 경우, 원래는 빙하였던 자리가 바다가 되면덜 녹아야 하는 다음 빙하가 더 녹게 되는 경우가 생겨 결과가 바뀔 수 있다.)1년치 녹고도 바다가 되지 않은 빙하는 다시 큐에 담아준다.1년치 모두 녹이고 난 뒤에 dfs를 돌고 dfs로 visited되지..

카테고리 없음 2024. 11. 29. 20:25

https://www.acmicpc.net/problem/2206예제 입력의 경우는 벽을 무조건 부숴야 목적지에 도착할 수 있는 형태로 나와있다. 문제 조건은 벽을 한번까지 부술 수 있다는 것이고 무조건 벽을 부숴야 하는 상황은 아니기에벽을 부수고가는 경로와 벽을 부수지 않고 가는 경로를 모두 확인해서 비교해볼 필요가 있다. 처음에는 일반적인 bfs의 큐에 들어가는 각 항목에 해당지점까지 가면서 벽을 깼는지 안깼는지를 위한 필드를 추가해서 관리해주면서 최대 1번까지 벽을 깰 수 있도록 구현했는데 이렇게 처리하게 된다면 벽을 깨지 않고 a 지점을 거쳤을 때 결론적으론 가장 짧은 루트더라도벽을 깨지 않았을 때 보다 벽을 깼을 때 a지점에 빠르게 도착한다면, a지점이 visited 처리 되어 벽을 깨지 않고 ..

baekjoon 2024. 11. 29. 19:47