[알고리즘] 백준 2146 Python

 

분류

BFS

혼자 힘으로 해결 했는가?

O

느낀 점

이번 문제는 해결하고도 왜 시간초과 없이 해결이 된 것인지 의아했다.

아니나 다를까 백준에서 문제에 대한 의견들을 찾아보니 나 처럼 이게 풀리다니... 하는 반응이었다.

 

처음 문제를 봤을 때, 각 섬들에 대해 BFS를 사용하여 마킹을 해두고

 

각 섬들마다 인접한 바다에서 BFS를 사용해서 최단거리를 brute force로 구하는 것이었다.

 

그러나 이는 러프하게 계산해도 N^4에 근사한 시간복잡도가 나와 절대 안 풀릴것 같았고

 

바다에서 BFS를 하는 방법 등 고민을 하다가 우선 처음 생각난 방법대로 구현을 해 보았다.

 

처음 구상한 방법도 구현 난이도가 쉽지는 않아서 구현 + BFS의 느낌이 강했다.

 

그런데... 이게 시간초과가 없이 풀려서 나도 놀라웠다.

 

처음 섬을 마킹하는 BFS를 제외하고 최단경로를 구할 때는 모든 그래프를 다 순회하는 것이 아니어서

시간초과가 생기지 않은 것인가... 생각이 들었다.

 

추가로, 내 풀이법에서 더 개선이 가능한 부분은 처음에 구해둔 minDist보다 작을떄 까지만 BFS를 진행하는 것이다.

그러나 나는 그냥 다 진행했는데도 풀렸다...

---

 

내가 작성한 코드

from sys import stdin
from collections import deque

N = int(input())

board = []

for i in range(N):
    board.append(list(map(int, stdin.readline().rstrip().split())))




findLand = deque()
endOfLand = deque()

dy = [-1,1,0,0]
dx = [0,0,-1,1]


def findBFS(count):
    while findLand:
        y, x = findLand.popleft()


        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]

            if 0 <= ny < N and 0 <= nx < N and board[ny][nx] == 0:
                if (ny, nx) not in endOfLand:
                    # print("sea Y : %d, sea X : %d" % (ny, nx))
                    endOfLand.append((ny, nx, count))

            if 0 <= ny < N and 0 <= nx < N and board[ny][nx] == 1:
                findLand.append((ny,nx))
                board[ny][nx] = count



num = 2
for i in range(N):
    for j in range(N):
        if board[i][j] == 1:
            findLand.append((i,j))
            board[i][j] = num
            findBFS(num)
            num += 1


# for i in board:
#     print(*i)
#
# print(*endOfLand)
minDist = 3000001


def findLoadBFS(number):
    global minDist
    while findLoad:
        y, x, dist = findLoad.popleft()

        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]

            if 0 <= ny < N and 0 <= nx < N:
                # 다른 섬이 발견 되면 멈춰!
                if board[ny][nx] != 0 and board[ny][nx] != number:
                    minDist = min(minDist, dist)
                    return
                elif board[ny][nx] == 0 and visit[ny][nx] == 0:
                    findLoad.append((ny,nx,dist + 1))
                    visit[ny][nx] = dist + 1


while endOfLand:
    visit = [[0 for _ in range(N)] for _ in range(N)]

    startY, startX, number = endOfLand.popleft()

    findLoad = deque()
    findLoad.append((startY, startX, 1))
    visit[startY][startX] = 1

    findLoadBFS(number)

    # print("statY : %d, statX : %d, min : %d" %(startY, startX, minDist))
    # for i in visit:
    #     print(*i)
    # print()

print(minDist)

 

 

 

---

비슷한 문제들