[백준] 2146 | 다리 만들기 | C++

풀이의 핵심은 이렇다.

int mem[][]에 섬의 번호 작성
int vis[][]에 다른 섬까지의 거리 작성
set<좌표> S[]로 출발섬의 끝 좌표 수집


1. DFS로 섬들의 번호를 매긴다, 끝 좌표들도 모아준다.
DFS(좌표, 번호):
	mem[좌표] <- 번호
    4방향 탐색:
    	새좌표 범위안?:
        	새 좌표가 아직 섬이고, mem[새좌표]에 작성안됨:
            	DFS(새좌표, 번호);
            새 좌표가 이제 섬이 아니고, mem[새좌표]는 작성안됨:
            	현재좌표는 섬의 끝좌표이므로 S[섬번호] <- 현재좌표 저장


2. BFS로 다른 섬까지의 거리를 작성한다. 섬에 닿으면 res 갱신
BFS(출발섬번호):
	vis <- -1 초기화(여러번 사용하기 때문)
    Q 준비,
    S[섬번호]에 저장된 좌표들 Q에 삽입
    
    while 큐:
    	현재좌표 꺼내기
        새좌표 만들기
        새좌표 범위안?:
        	vis[새좌표]가 -1?:
            	vis[새좌표]에 거리값 넣기
                Q 삽입
                만약 새좌표가 섬인데 출발섬번호와 다르다?:
                	res <- vis[현재좌표]와 min 갱신

 

영상설명

 

 

정답 소스코드