[python] 백준 2146번 : 다리 만들기 (bfs)

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

2146번: 다리 만들기

 

1. 구현

from collections import deque

n = int(input())
bridge = [list(map(int, input().split())) for _ in range(n)]
last_x, last_y = 0, 0
for i in range(n):
    for j in range(n):
        if bridge[i][j] == 1:
            last_x, last_y = i, j
move = [(1, 0), (0, 1), (0, -1), (-1, 0)]

def myArea(x, y, color):
    que = deque([(x, y)])
    bridge[x][y] = color
    my_area = [(x, y)]
    while que:
        x, y = que.popleft()
        for dx, dy in move:
            nx = dx + x
            ny = dy + y
            if 0 <= nx < n and 0 <= ny < n:
                if bridge[nx][ny] == 1:
                    bridge[nx][ny] = color
                    que.append((nx, ny))
                    my_area.append((nx, ny))
    return my_area

def getMinDistance(my_area, color):
    global result
    distance = [[-1] * n for _ in range(n)]

    for x, y in my_area:
        distance[x][y] = 0
    que = deque(my_area)
    while que:
        x, y = que.popleft()
        for dx, dy in move:
            nx, ny = x + dx, y + dy
            if nx < 0 or nx >= n or ny < 0 or ny >= n:
                continue
            # 본인 섬이 아닌 새로운 섬에 도달한다면    
            if bridge[nx][ny] > 0 and bridge[nx][ny] != color:
                result = min(result, distance[x][y])
                return
            # 바다를 만난 경우 +1 증가
            if bridge[nx][ny] == 0 and distance[nx][ny] == -1:
                distance[nx][ny] = distance[x][y] + 1
                que.append((nx, ny))

result = 1e9
c = 26

for i in range(n):
    for j in range(n):
        area = []
        if bridge[i][j] == 1:
            # 본인 섬 색칠 (다른 섬이랑 구분할 수 있도록)
            c += 1
            area = myArea(i, j, c)
            # 마지막 섬에 도달한 경우
            if (last_x, last_y) in area:
                break
            getMinDistance(area, c)
print(result)

섬이랑 가장 가까운 거리를 구하는 함수인 getMinDistance를 잘 구현하지 못했다.

 

2. 틀린 풀이

def getMinDistance(my_area, color):
    global cnt
    for x, y in my_area:
        i, j = x, y
        for dx, dy in move:
            while True:
                x += dx + x
                y += dy + y
                if x >= n or x < 0 or y >= n or y < 0:
                    break
                if bridge[x][y] != 0 and bridge != color:
                    distance = abs(i-x)**2 + abs(j-y)**2
                    cnt = min(cnt, distance)

 

def getMinDistance(my_area, color):
    global cnt
    for x, y in my_area:
        que = deque([(x, y, 0)])
        while que:
            x, y, c = que.popleft()
            for dx, dy in move:
                nx, ny = x + dx, y + dy
                if 0 <= nx < n and 0 <= ny < n:
                    if bridge[nx][ny] == 1:
                        return c
                    que.append((nx, ny, c+1))