[BOJ] 2146. 다리만들기 Python

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

2146번: 다리 만들기

 

 

1. 해결방법

BFS 문제이다..
쉬울줄 알았는데 어려웠다.

2개의 큐를 사용해야 하고, 시간 복잡도를 고려해야 한다.
시간나면 다시 한번 풀어봐야겠다.

1. 각 섬을 구분짓기 위해 bfs1을 돌아서 각 섬들이 고유의 번호를 갖기 위해 값을 하나씩 증가시켜 maps을 저장했다.
2. 2중 for문으로 특정 섬부터 시작해서 두 번째 bfs2를 돈다.
3. 유효성 검사를 하고 자신의 섬이 아닌 다른 섬을 찾았다면 return
4. 다른 섬이 아닌 바다라면, 해당 인덱스 위치와 cnt + 1로 다리를 하나 더 만들었다는 변수를 추가로 append한다.
5. answer의 값 비교를 한다. 

 

 

2. 정답코드

import sys
from collections import deque

input = sys.stdin.readline

N = int(input())
maps = [list(map(int, input().split())) for _ in range(N)]

dy, dx = (1, -1, 0, 0), (0, 0, 1, -1)


def bfs1(y, x):
    global count

    q = deque()
    q.append((y, x))
    chk[y][x] = True
    maps[y][x] = count

    while q:
        ey, ex = q.popleft()
        for d in range(4):
            ny, nx = ey + dy[d], ex + dx[d]
            if 0 <= ny < N and 0 <= nx < N and chk[ny][nx] == False and maps[ny][nx] == 1:
                chk[ny][nx] = True
                maps[ny][nx] = count
                q.append((ny, nx))


def bfs2(y, x, v):
    q = deque()
    q.append((y, x, 0))

    while q:
        ey, ex, cnt = q.popleft()
        if maps[ey][ex] != 0 and maps[ey][ex] != v:
            return cnt - 1

        for d in range(4):
            ny, nx = ey + dy[d], ex + dx[d]
            if 0 <= ny < N and 0 <= nx < N and chk[ny][nx] == False and maps[ny][nx] != v:
                chk[ny][nx] = True
                q.append((ny, nx, cnt + 1))
    return 1e9


chk = [[False] * N for _ in range(N)]
count = 1
for i in range(N):
    for j in range(N):
        if chk[i][j] == False and maps[i][j] == 1:
            bfs1(i, j)
            count += 1

answer = 1e9
for i in range(N):
    for j in range(N):
        if maps[i][j] != 0:
            chk = [[False] * N for _ in range(N)]
            answer = min(answer, bfs2(i, j, maps[i][j]))


print(answer)