백준 2146번 - 다리 만들기(python)

https://www.acmicpc.net/problem/2146

2146번: 다리 만들기

 

우선 해당 문제의 사고 과정은 다음과 같다.

1. A라는 섬과 B라는 섬이 있을 때, 두 섬은 구분이 되어야하는가?  → 그렇다.
2. 그렇다면 구분은 어떻게 할까? → 숫자를 1, 2, 3 이런 식으로 구분시키자.
3. 이제 섬 영역들 하나씩 BFS를 돌리자. 

우선 각 섬 구분은 bfs를 돌리면서 진행했다.

def divide_bfs(x, y):
    q = deque()
    q.append((x, y))
    visited[x][y] = True
    global count
    count += 1
    graph[x][y] = count
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < N:
                if graph[nx][ny] != 0 and visited[nx][ny] == False:
                    visited[nx][ny] = True
                    graph[nx][ny] = graph[x][y]	# 섬의 숫자로 변경해주기
                    q.append((nx, ny))
                    
count = 0
visited = [[False for _ in range(N)] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if graph[i][j] != 0 and visited[i][j] == False:
            divide_bfs(i, j)

그냥 일반적인 BFS를 하면서, 해당 영역을 섬의 숫자로 바꾸어주었다.

 

그 다음에는 각 섬 영역들로부터 bfs를 돌리면서, 다른 섬을 만날 때까지 얼마나 칸을 지나가야 하는지 확인해야한다.

def bfs(x, y):
    q = deque()
    dist = [[-1 for _ in range(N)] for _ in range(N)]
    q.append((x, y))
    n = graph[x][y]
    dist[x][y] = 0
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < N:
                if graph[nx][ny] > 0 and graph[nx][ny] != n:
                    return dist[x][y]
                if graph[nx][ny] == 0 and dist[nx][ny] == -1:
                    dist[nx][ny] = dist[x][y] + 1
                    q.append((nx, ny))
    return sys.maxsize
    
# 2. 각 섬들 좌표에서 다른 섬 만나기 최소화
result = sys.maxsize
for i in range(N):
    for j in range(N):
        if graph[i][j] != 0:
            result = min(result, bfs(i, j))
print(result)

옆의 칸이 0보다 크면서 동시에 기존의 칸의 숫자와 다르다면, 새로운 섬을 만난 것이다. 그렇기에 지금까지의 거리를 반환해준다.

만약 옆의 칸이 0이면서 거리가 -1이라면, 아직 방문하지 않은 바다이므로 큐에 넣어주고 거리를 증가시켜준다.

 

 

정답 코드)

from collections import deque
import sys


def divide_bfs(x, y):
    q = deque()
    q.append((x, y))
    visited[x][y] = True
    global count
    count += 1
    graph[x][y] = count
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < N:
                if graph[nx][ny] != 0 and visited[nx][ny] == False:
                    visited[nx][ny] = True
                    graph[nx][ny] = graph[x][y]
                    q.append((nx, ny))


def bfs(x, y):
    q = deque()
    dist = [[-1 for _ in range(N)] for _ in range(N)]
    q.append((x, y))
    n = graph[x][y]
    dist[x][y] = 0
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < N:
                if graph[nx][ny] > 0 and graph[nx][ny] != n:
                    return dist[x][y]
                if graph[nx][ny] == 0 and dist[nx][ny] == -1:
                    dist[nx][ny] = dist[x][y] + 1
                    q.append((nx, ny))
    return sys.maxsize


N = int(input())
graph = []
for _ in range(N):
    graph.append(list(map(int, input().split())))
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

# 1. 섬들을 다른 걸로 분리 (1, 2, 3, ...)
count = 0
visited = [[False for _ in range(N)] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if graph[i][j] != 0 and visited[i][j] == False:
            divide_bfs(i, j)

# 2. 각 섬들 좌표에서 다른 섬 만나기 최소화
result = sys.maxsize
for i in range(N):
    for j in range(N):
        if graph[i][j] != 0:
            result = min(result, bfs(i, j))
print(result)

 

가져가야할 점)

1. 섬들을 구분시켜줘야하는지의 여부는 생각해보자.

2. 파이썬에서 값의 최대는 sys.maxsize로 가져올 수 있다.

3. 거리 등의 문제가 나오면 count 변수보다는 거리 배열을 만들어서 활용하자.