https://www.acmicpc.net/problem/2146
2146번: 다리 만들기여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다www.acmicpc.net
어제 이걸못풀어서 접을까 생각했다.
일단, 모든 섬을 구분한다. (bfs1)
섬의 가장자리(edge)좌표를 모두 구한다.
edge를 바탕으로 (bfs2) 를 진행하며, 바다를 그 섬으로 메워나간다
bridge배열을 만들어서, 메운 위치에 1씩 +하며 메운 점 갯수를 센다.
메워나가다가, 만일 자기 섬도 아니고 바다도 아닌 다른 섬을 만나면 이제 다리가 이어진것이다.
그러면 bridge의 현위치+만난위치가 경로이다.
여기서 한참을 헤멨는데,
당연히 먼져 도달한 것이 최소경로라고 생각했다. 하지만……
5
1 0 0 0 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 1 0 0 1
다음과같은 반례가 있다. 최소경로는 4,2 4,3 을 이은 2이지만,
문제는 먼져 왼쪽위와 오른쪽위가 디큐에 들어가므로, 맨 아랫쪽보다 먼져 만나게 된다.
그래서 answer과 만났을때의 합을 계속 비교하며, 최솟값을 찾는 식으로 풀었다.
다시풀으라고하면 또 잊어버려서 헤멜거같다.
import sysinput=sys.stdin.readlinefrom collections import deque
moves=[(-1,0),(1,0),(0,-1),(0,1)]def bfs1(i,j,num): #섬클러스터링 que=deque()
arr[i][j]=num que.append((i,j)) while que: i,j=que.popleft()
for a,b in moves: tmp_i,tmp_j=i+a,j+b
if 0<=tmp_i<n and 0<=tmp_j<n :
if arr[tmp_i][tmp_j]==1:
arr[tmp_i][tmp_j]=num
que.append((tmp_i,tmp_j))
elif arr[tmp_i][tmp_j]==0:
edge.append((i,j,num,0)) returndef dfs2(): #다리놓기
global answer queque=deque(edge) while queque:
i,j,num,cnt=queque.popleft() for a,b in moves:
tmp_i,tmp_j=i+a,j+b if 0<=tmp_i<n and 0<=tmp_j<n:
if arr[tmp_i][tmp_j]==0:
arr[tmp_i][tmp_j]=num
brigde[tmp_i][tmp_j]=cnt+1
queque.append((tmp_i,tmp_j,num,cnt+1))
elif arr[tmp_i][tmp_j]!=num:
answer=min(answer,cnt+brigde[tmp_i][tmp_j])
answer=1e+10n=int(input())
arr=[ [* map (int,input().split())]for _ in range(n)]
brigde=[[False for _ in range(n)]for _ in range(n)]num=2edge=[]
for i in range(n): for j in range(n): if arr[i][j]==1:
bfs1(i,j,num) num+=1 else: continue
edge=list(set(edge))dfs2()print(answer)