[BOJ] 2146번 다리만들기 / 사용언어 : 파이썬(python)

※ 문제링크

2146번: 다리 만들기

해당문제는 BFS를 활용하여 해결할 수 있는 문제였다. 처음 생각한 방법은 완전 탐색을 통해 섬의 좌표값을 모두 확인한 후 BFS함수를 한번씩 돌려가며 다른 섬에서 출발한 다리와 만날때 cnt값을 반환하는 것이었는데, 해당 방식으로 구현하면 다리의 길이가 될 수 있는 경우의 수가 2개가 되어 정확한 값을 구하지 못하는 문제가 있어 각 섬에 고유번호를 부여하고, 맵의 각 좌표의 방문기록을 일일히 기록하며, 섬의 번호가 다른 지점이 발생할 때, 각 섬에서 출발한 다리길이의 숫자를 구해서 리턴하는 방식으로 구현하였다. 자세한 풀이방법과 코드는 아래와 같다.

1. 입력받은 값을 2차원 배열로 변환하여 그래프 형태로 만들어준다.

2. 각각의 섬에 고유번호를 부여할 BFS함수와 지도의 각 지점의 방문기록을 확인할 2차원 배열을 만들어 준 후 섬에 번호를 부여한다.

3. 각 섬에서 출발한 다리의 길이를 기록할 2차원 배열을 만들고, 섬과 다리설치여부를 확인할 BFS함수를 작성해준다.

4. 반복문을 통해 다리가 만나는 지점이 발생할 때 해당 다리의 총 길이를 구하고, 다리의 총 길이를 기록한 리스트에서 최소값을 반환하여 출력해준다.

+ 시간 및 메모리 단축을 위해 sys를 사용하였으며, 개행문자에 유의하였다.

 

from collections import deque
import sys

# input = sys.stdin.readline
N = int(input())
field = []
for _ in range(N):
    field.append(list(map(int, input().split())))

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
visited = [[False for _ in range(N)] for _ in range(N)]
length = [[0 for _ in range(N)] for _ in range(N)]
queue = deque()

def check_island(x, y, island_num):
    island = deque()
    visited[y][x] = True
    island.append([x, y])
    field[y][x] = island_num
    queue.append([x, y, island_num])

    while island:
        x, y = island.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < N:
                if field[ny][nx] == 1 and visited[ny][nx] == False:
                    field[ny][nx] = island_num
                    visited[ny][nx] = True
                    island.append([nx, ny])
                    queue.append([nx, ny, island_num])

def bridge():
    ans_list = []
    for _ in range(len(queue)):
        x, y, island_num = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < N:
                if field[ny][nx] == 0 and visited[ny][nx] == False:
                    visited[ny][nx] = True
                    field[ny][nx] = island_num
                    length[ny][nx] = cnt
                    queue.append([nx, ny, island_num])
                if field[ny][nx] != 0 and island_num != field[ny][nx]:
                    ans_list.append(length[ny][nx] + length[y][x])
    if len(ans_list) != 0:
        return min(ans_list)
    return 0

island_num = 1
queue = deque()
for i in range(N):
    for k in range(N):
        if field[k][i] == 1 and visited[k][i] == False:
            check_island(i, k, island_num)
            island_num += 1

ans = 0
cnt = 0
while ans == 0:
    cnt += 1
    ans = bridge()
print(ans)

 

P.S 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.