tmdwp54977   1달 전

각 함수의 역할은

bfsRemap() : 처음에 모두 1로 들어왔던 섬 정보에 대해, 서로 다른 섬에 속하는 요소들은 서로 다른 숫자로 바꿔주는 함수

bfsBridge() : bridge_visit[][] == 0이면서 주위 네 방향에 대해 섬이 존재한다면, 해당 지점에서 BFS를 돌려 가장 짧은 다리 찾기

각 변수들의 역할은

map : 땅 정보 저장

bridge : 더 짧은 다리 길이를 저장하는 변수

length[] : 가장 짧은 다리를 BFS로 찾을 때 다리 길이를 저장하는 queue

bridge_visit[][] : bfsRemap() 실행 후, map 값이 0인 지점들에 대한 방문 여부 체크

입니다.


visit[][]을 bfsBridge()가 실행될 때마다 초기화 시켜줬고, 직접 값을 찍어보면서 주위 네 방향 중 한 방향이라도 섬이 존재하는 경우에만 bfsBridge()가 실행된다는 것도 확인했습니다. queue가 다 빌 때까지 계속 수행하여 더 짧은 값을 찾지 못하고 끝나는 경우도 없습니다. 결국 bfsBridge() 내 46 ~ 60번째 줄 내에 오류가 있다고 생각했는데, 제 논리에 대한 반례가 언제인지 궁금합니다. 혹은 다른 부분에서 실수하고 있는 것이 있다면 알려주세요.


Line 46 : 현재 좌표 값에 대해 +dx, +dy를 했을 때 맵을 벗어나는 값이 있다면 해당 경우는 더이상 탐색할 필요가 없으므로 continue

Line 49 : 현재 좌표 값에 대해 +dx, +dy를 했을 때 해당 지점이 0이 아닌 값, 즉 육지라면

              Line 50 : 그 값이 bfsBridge()의 세번째 인자인 island와 다르다면, 즉 다른 섬을 만났고 해당 지점까지의 다리 길이가 더 짧다면 bridge를 갱신 
              해당 지점이 island와 같든 다르든, 해당 방향으로 +dx, +dy를 해봤자 Line 55에 의해 queue에 들어가지 않으므로 반드시 continue

Line 55 : visit은 map[][] == 0일때, 즉 바다에 대해서만 수행함

댓글을 작성하려면 로그인해야 합니다.