[문제풀이-백준] 17472. 다리만들기2

풀이

아이디어 및 구현방법

• 각 섬들의 번호 붙이기

  • bfs

• 다리 만들기 (bfs 이용)

  • 처음에 들어온 좌표에서 네 방향 탐색해서 바다인 곳만 덱에 넣고 방향정보까지 같이 넣어줌
  • 같이 넣어준 방향만 이동하며 탐색
  • 길이가 2이상이고, 자기 섬이면 안된다
  • 위 조건이 없으면 바다로 나아감

• 어떠한 섬을 연결해야 최소가 나오지? (Prim 알고리즘 적용)

  • 모든 노드가 연결되야하기 때문에 최소신장트리라고 생각
  • prim 알고리즘으로 접근
    • 최소 다리 갯수로 계속 갱신해야하므로 인접리스트보단 인접행렬 사용
    • 1번 섬을 최초 섬으로 선택
    • 갈 수 있는 최소비용 값 갱신
    • 가지 않았으면서 최소인 값을 현재 노드로 선택
    • 위 두 과정 반복

참고

• prim 알고리즘에서 최솟값을 찾을때, 리스트의 크기가 작다면 heapq보다 반복문 돌리는 것이 더 빠름

코드

Python

from _collections import deque

def change(y,x,v):
    deq = deque()
    deq.append((y,x,v))
    matrix[y][x] = v
    visited[y][x] = 1
    while deq:
        here = deq.popleft()
        y,x,v = here[0],here[1],here[2]
        for dir in range(4):
            ny,nx = y+direct[dir][0],x+direct[dir][1]
            if 0<=ny<N and 0<=nx<M and not visited[ny][nx] and matrix[ny][nx]:
                deq.append((ny,nx,v))
                visited[ny][nx] = 1
                matrix[ny][nx] = v


def bfs(y,x,c,v):
    deq = deque()
    for dir in range(4):
        ny,nx = y+direct[dir][0],x+direct[dir][1]
        if 0<=ny<N and 0<=nx<M and not matrix[ny][nx]:
            deq.append((ny,nx,c+1,dir))
    while deq:
        here = deq.popleft()
        y,x,c,dir = here[0],here[1],here[2],here[3]
        ny,nx = y+direct[dir][0],x+direct[dir][1]
        if 0<=ny<N and 0<=nx<M and c>=2 and matrix[ny][nx] and matrix[ny][nx]!=v and c < adj[v][matrix[ny][nx]]:
            adj[v][matrix[ny][nx]] = c
            adj[matrix[ny][nx]][v] = c
        elif 0<=ny<N and 0<=nx<M and not matrix[ny][nx]:
            deq.append((ny,nx,c+1,dir))


direct = [(-1,0),(0,1),(1,0),(0,-1)]
N,M = map(int,input().split())
matrix = [list(map(int,input().split())) for _ in range(N)]
visited = [[0]*M for _ in range(N)]
INF = float('inf')
count = 0

for i in range(N):
    for j in range(M):
        if not visited[i][j] and matrix[i][j]:
            count += 1
            change(i,j,count)
            
adj = [[INF]*(count+1) for _ in range(count+1)]
for i in range(N):
    for j in range(M):
        if matrix[i][j]:
            bfs(i,j,0,matrix[i][j])
            
mst = [0]*(count+1)
key = [INF]*(count+1)
key[1] = 0
cnt = result = 0
while cnt<count:
    min = INF
    for i in range(1, count+1):
        if not mst[i] and key[i] < min:
            min = key[i]
            u = i
    mst[u] = 1
    result += min
    cnt += 1
    for w in range(1,count+1):
        if not mst[w] and adj[u][w] < key[w]:
            key[w] = adj[u][w]
            
if result<INF:
    print(result)
else:
    print(-1)

Python_PriorityQ

from _collections import deque
import heapq


def change(y,x,v):
    deq = deque()
    deq.append((y,x,v))
    matrix[y][x] = v
    visited[y][x] = 1
    while deq:
        here = deq.popleft()
        y,x,v = here[0],here[1],here[2]
        for dir in range(4):
            ny,nx = y+direct[dir][0],x+direct[dir][1]
            if 0<=ny<N and 0<=nx<M and not visited[ny][nx] and matrix[ny][nx]:
                deq.append((ny,nx,v))
                visited[ny][nx] = 1
                matrix[ny][nx] = v


def bfs(y,x,c,v):
    deq = deque()
    for dir in range(4):
        ny,nx = y+direct[dir][0],x+direct[dir][1]
        if 0<=ny<N and 0<=nx<M and not matrix[ny][nx]:
            deq.append((ny,nx,c+1,dir))
    while deq:
        here = deq.popleft()
        y,x,c,dir = here[0],here[1],here[2],here[3]
        ny,nx = y+direct[dir][0],x+direct[dir][1]
        if 0<=ny<N and 0<=nx<M and c>=2 and matrix[ny][nx] and matrix[ny][nx]!=v and c < adj[v][matrix[ny][nx]]:
            adj[v][matrix[ny][nx]] = c
            adj[matrix[ny][nx]][v] = c
        elif 0<=ny<N and 0<=nx<M and not matrix[ny][nx]:
            deq.append((ny,nx,c+1,dir))


direct = [(-1,0),(0,1),(1,0),(0,-1)]
N,M = map(int,input().split())
matrix = [list(map(int,input().split())) for _ in range(N)]
visited = [[0]*M for _ in range(N)]
INF = float('inf')
count = 0

for i in range(N):
    for j in range(M):
        if not visited[i][j] and matrix[i][j]:
            count += 1
            change(i,j,count)

adj = [[INF]*(count+1) for _ in range(count+1)]
for i in range(N):
    for j in range(M):
        if matrix[i][j]:
            bfs(i,j,0,matrix[i][j])

heap = []
mst = [0]*(count+1)
key = [INF]*(count+1)
key[1] = 0
result = 0
heapq.heappush(heap, (0,1))
while heap:
    min,u = heapq.heappop(heap)
    if mst[u]: continue
    mst[u] = 1
    result += min
    for w in range(1,count+1):
        if not mst[w] and adj[u][w] < key[w]:
            key[w] = adj[u][w]
            heapq.heappush(heap, (key[w],w))

for i in range(1,count+1):
    if not mst[i]:
        print(-1)
        break
else:
    print(result)

java

import java.util.*;
import java.io.*;

public class Main17472_다리만들기2 {
	static int N,M;
	static int[][] matrix;
	static int[][] adj;
	static boolean[] mst;
	static int[] key;
	static boolean[][] visited;
	static Queue<int[] > q;
	static int[][] direct = {
			{-1,0},
			{0,1},
			{1,0},
			{0,-1},
	};
	public static void change(int y, int x, int number) {
		int ny,nx,dir;
		q = new LinkedList<>();
		q.offer(new int[] {y,x});
		visited[y][x] = true;
		matrix[y][x] = number;
		while(!q.isEmpty()) {
			int[] here = q.poll();
			for (dir=0; dir<4; dir++) {
				ny = here[0] + direct[dir][0];
				nx = here[1] + direct[dir][1];
				if (0 <= ny && ny<N && 0 <= nx && nx < M && matrix[ny][nx] == 1 && !visited[ny][nx]) {
					matrix[ny][nx] = number;
					q.offer(new int[] {ny,nx});
					visited[ny][nx] = true;
				}
			}
		}
	}
	
	public static void bfs(int y, int x, int c, int v) {
		int ny,nx,dir;
		q = new LinkedList<>();
		for (dir=0; dir<4; dir++) {
			ny = y + direct[dir][0];
			nx = x + direct[dir][1];
			if (0 <= ny && ny<N && 0 <= nx && nx < M && matrix[ny][nx]==0) {
				q.offer(new int[] {ny,nx,c+1,dir});
			}
		}
		while (!q.isEmpty()) {
			int[] here = q.poll();
			ny = here[0] + direct[here[3]][0];
			nx = here[1] + direct[here[3]][1];
			c = here[2];
			if (0 <= ny && ny<N && 0 <= nx && nx < M && matrix[ny][nx]>0 && matrix[ny][nx]!=v && c >= 2 && c < adj[v][matrix[ny][nx]]) {
				adj[v][matrix[ny][nx]] = c;
				adj[matrix[ny][nx]][v] = c;
			} else if (0 <= ny && ny<N && 0 <= nx && nx < M && matrix[ny][nx] == 0) {
				q.offer(new int[] {ny,nx,c+1,here[3]});
			}
		}
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		matrix = new int[N][M];
		visited = new boolean[N][M];
		int i,j,num,min,result,cnt,u;
		for (i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (j=0; j<M; j++) {
				matrix[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		num = 0;
		for (i=0; i<N; i++) {
			for (j=0; j<M; j++) {
				if (matrix[i][j] > 0 && !visited[i][j]) {
					num ++;
					change(i,j,num);
				}
			}
		}
		
		adj = new int[num+1][num+1];
		for (i=0; i<num+1; i++) {
			for (j=0; j<num+1; j++) {
				adj[i][j] = 1000;
			}
		}
		for (i=0; i<N; i++) {
			for (j=0; j<M; j++) {
				if (matrix[i][j] > 0) {
					bfs(i,j,0,matrix[i][j]);
				}
			}
		}
		mst = new boolean[num+1];
		key = new int[num+1];
		for (i=0; i < num+1; i++) {
			key[i] = 1000;
		}
		key[1] = 0;
		result = 0;
		cnt = 0;
		u = 0;
		while (cnt<num) {
			min = 1000;
			for (i=1; i<num+1; i++) {
				if (!mst[i] && key[i] < min) {
					min = key[i];
					u = i;
				}
			}
			mst[u] = true;
			result += min;
			cnt ++;
			for (int w=1; w<num+1; w++) {
				if (!mst[w] && adj[u][w] < key[w]) {
					key[w] = adj[u][w];
				}
			}
		}
		if (result<1000) {
			System.out.println(result);
		} else {
			System.out.println(-1);
		}
		
	}

}