allgoodlife   8달 전

다리를 만드는 문제인데ㅋㅋㅋ

아래 주석을 열심히 달았어요.

testcase 다 잘나오고 예외처리도 했다고 생각했는데 바로 틀렸다고하는데.. 꽃미남님들 알려주세요~~

제 코드의 흐름

1. 입력받는다.

2. dfs로 섬들에게 번호를 붙여준다. & dfs호출개수를 통해 섬의 개수를 세어준다

3. 2에서 세어준 섬의개수가 2개이상일경우 5로 진행.

  (섬이 0-1개인 경우 다리가 필요 없으므로 0을 출력하고 나온다)

4. bfs를 통해 각 섬들을 돌아가면서 한칸씩 간척사업을 진행한다.

--> 간척사업을 진행하다가 다른 섬의 번호가 주변에 있으면 그 두 개 번호의 합을 답으로 저장한다.

5. 답을 출력한다.


오늘 너무 시간을 많이썼네요 ㅠㅠ

조언 부탁드립니다~~

zlzmsrhak   8달 전

반례입니다.

3
1 0 0 1
0 0 0 0
1 0 1 0
0 0 0 0


구체적으로 이유를 쓰면 섬은 아래처럼 되고,

1 0 0 2

0 0 0 0

3 0 4 0

0 0 0 0

1과 2를 한번 확장하면

1 1 2 2

1 0 0 2

3 0 4 0

0 0 0 0

처럼 되어 다리 2짜리를 찾았다고 생각하고 프로그램을 종료시킵니다.

allgoodlife   8달 전

zlzmsrhak님께 감사의 말씀드립니다.

nano6384   2달 전

음 저는 각 섬마다 바다에 닿는 부분을 dfs를 통해 찾아서 번호를 다르게 붙여줬어요.

바다에 닿는 부분이 다리를 건설할 수 있는 부분이니까요. 이들을 후보지라고 부른다면...

예를 들어 1번 섬의 후보지들은 1번으로, 2번 섬들의 후보지들은 2번으로... 이걸 저장할 2차원 배열을 하나 더 만들어서 저장했습니다.


그리고 각 후보지들에서 bfs로 가장 짧은 경로를 찾았고 현재까지 찾은 최단 경로보다 같거나 넘어가면 가지치기도 시도해봤어요.


더 좋은 방법 알고 계시면 알려주시면 감사하겠습니당 ㅎㅎ

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