[BFS, 파이썬] 2146. 다리만들기 (!!)

 

1차 코드 결과(메모리초과), 2차 코드 결과 (실행시간 3344ms)

3차 코드 (개선 후 실행시간 176ms)

메모리 초과 ➔ 정답처리 ➔ 개선

 

분석한 차이점

• 메모리 초과 케이스 (1차코드) :
  • 56번쯤 라인에 바다 & 거리값 입력 안되어있으면 지금까지 온 거리 +1 이랑 기존 입력값이랑 min 비교하는데, 안해도 됨.. . BFS가 어떤 식으로 전개되는지 잘 안그려진다. 이 조건이 2차 코드에서 왜 없어도 되는지 이해가 잘 안간다.  BFS는 칸마다 최단거리로 채워진다는 특징 때문인듯, 이미 방문했으면 굳이 안채워도 되나봐
  • secChecked 라고 구획을 그린 그래프를 별도로 두고, 이거로 visited도 판단함.. 그래프가 커질수록 부하가 걸렸나
    => 메모리 초과의 원인인 듯
• 정답처리 된 케이스 (2차코드) :
  • 섬 입력받은 표에 그대로 구획을 표시한거로 활용하고, visited True False 로 접근해서 썼음

 

• 메모리 획기적으로 줄인 케이스 (3차코드) : 1차 BFS 도는 for 문에 break 추가... 아직 이유는 모르겠다

 

1차 코드

import sys
from collections import deque

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

SEA = 0
EARTH = 1

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

q = deque()
q.append((0, 0))

secChecked = [[0] * N for _ in range(N)]  # point!


def drawSector(start, sector):
    q = deque()
    q.append(start)
    while q:
        x, y = q.popleft()
        secChecked[x][y] = sector
        for move in range(4):
            nx, ny = x + dx[move], y + dy[move]
            if 0 <= nx < N and 0 <= ny < N:
                if island[nx][ny] == EARTH and secChecked[nx][ny] == 0:  # point!
                    q.append((nx, ny))


def makeBridge(sec):
    global bridge
    dist = [[-1] * N for _ in range(N)]
    adventure = deque()

    for i in range(N):
        for j in range(N):
            if secChecked[i][j] == sec:
                adventure.append([i, j])
                dist[i][j] = 0

    while adventure:
        x, y = adventure.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < N and 0 <= ny < N:
                if secChecked[nx][ny] != 0 and secChecked[nx][ny] != sec:
                    # 내구역 아닌 땅 만나면
                    bridge = min(dist[x][y], bridge)
                    return

                if island[nx][ny] == SEA:
                    # 바다 만나면
                    dist[nx][ny] = (
                        min(dist[x][y] + 1, dist[nx][ny]) if dist[nx][ny] != -1 else dist[x][y] + 1
                    )  # point!
                    adventure.append([nx, ny])


sector = 1
bridge = 10**5
for x in range(N):
    for y in range(N):
        if secChecked[x][y] == 0 and island[x][y] == EARTH:
            drawSector((x, y), sector)
            sector += 1

# 한번더 탐색하면서 다리 그리기
for sec in range(1, sector):
    makeBridge(sec)
print(bridge)

 

2차 코드, 3차 코드

import sys
from collections import deque

# sys.stdin = open("./input.txt", "rt")
input = sys.stdin.readline
N = int(input())
island = [list(map(int, input().split())) for _ in range(N)]

SEA = 0
EARTH = 1

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

q = deque()
q.append((0, 0))

visited = [[False] * N for _ in range(N)]


def drawSector(start, sector):
    q = deque()
    q.append(start)
    while q:
        x, y = q.popleft()
        visited[x][y] = True
        island[x][y] = sector
        for move in range(4):
            nx, ny = x + dx[move], y + dy[move]
            if 0 <= nx < N and 0 <= ny < N and island[nx][ny] == EARTH and not visited[nx][ny]:
                visited[nx][ny] = True
                island[nx][ny] = sector
                q.append((nx, ny))


def makeBridge(sec):
    global bridge
    dist = [[-1] * N for _ in range(N)]
    adventure = deque()

    for i in range(N):
        for j in range(N):
            if island[i][j] == sec:
                adventure.append([i, j])
                dist[i][j] = 0

    while adventure:
        x, y = adventure.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < N and 0 <= ny < N:
                if island[nx][ny] != 0 and island[nx][ny] != sec:
                    # 내구역 아닌 땅 만나면
                    bridge = min(dist[x][y], bridge)
                    return

                if island[nx][ny] == SEA and dist[nx][ny] == -1:
                    # 바다 만나면
                    dist[nx][ny] = dist[x][y] + 1
                    adventure.append([nx, ny])


sector = 1
bridge = 10**5
for x in range(N):
    for y in range(N):
        if (not visited[x][y]) and island[x][y] == EARTH:
            drawSector((x, y), sector)
            sector += 1
            # break  # 주석 풀면 3차 코드

# 한번더 탐색하면서 다리 그리기
for sec in range(1, sector):
    makeBridge(sec)
print(bridge)

 

 

git hub 코드

 

GitHub - namnameeroo/boj-algorithm: This is a auto push repository for Baekjoon Online Judge created with [BaekjoonHub](https://