rud15dns   9달 전

해당 문제를 풀면서, 의문점이 생겨 질문드립니다.

섬의 모든 가장자리 부분을 Queue에 담은 다음, 해당 Queue에 대해서 BFS를 시켰습니다.

각 섬에서 모든 가장자리가 순서대로 영역을 넓혀가면서, 처음으로 만나는 순간의 서로의 거리를 더한 것이 answer라고 생각했습니다. 

그러나, 이렇게 문제를 풀면 75%에서 답이 틀렸다고 뜹니다. 

그래서 answer를 바로 return 하지 않고, 최솟값을 찾게 한 후 마지막에 출력하였더니 정답이라고 뜹니다. 

제가 생각하기에 BFS에서는 모두 같은 거리인 점들부터 Queue에 들어가는 것으로 아는데, 

서로 다른 섬에서 같은 거리씩 전진하다가, 먼저 만나면 그게 최소 거리가 되는 게 아닌 것인가요?

(아래의 코드는 answer의 최솟값을 찾은 후 출력하는 정답 코드입니다.)

tkvl94   9달 전

선생님 코드는 각각의 섬마다 외곽을 넣은게 아니라 맵 전체를 기준으로 순차적으로 넣습니다.

간단하게 설명 드리면 아래 같은 지도가 주어지면

1 1 0 0 0 1
1 1 0 0 0 1
1 0 0 1 1 1

큐 자체가 1바퀴는 무난하게 도는데요.
2번째 바퀴에서 
vis배열 [0]기준

0 0 1 0 1 0 이런 형태에서  

0 0 1 2 1 0 이되고 

그 다음에 Q에서 꺼내는 게 [0][5]에 있는 1을 꺼내서 2를 보고 3을 반환합니다.

근데 이 맵을 밑에까지 보면
2칸으로 연결될 수 있다는걸 아실겁니다.

만약 각각의 섬의 외각끼리로 계산하고 싶으시면
1번 섬 외각 위치정보를 가진 배열
2번 섬 외각 위치정보를 가진 배열 ...
해놓으셨다가 큐에 넣으실때 1번섬 외각 전부 넣고 2번섬 외각 전부 넣고 이런식으로 하셔야합니다.

그리고 언어 선택 C++로 잘못 되어있습니다.

도움이 되셨다면 좋겠네요.
설명을 잘 하는편이 아니라서... 좀 허접한 설명으로 드렸습니다.

rud15dns   9달 전

와 정말 진심으로 감사합니다.

제가 섬을 기준으로 넣었다고 생각하고, BFS를 돌리니까 이해가 잘 안 되었습니다.

겹쳐지는 부분이 생겼을 때, 해당 레벨 대의 모든 좌표를 확인한 다음, 그 레벨의 최솟값이 정답이 되는거군요

예시 덕분에 이해가 되었습니다.

감사합니다!

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