[백준알고리즘] 2146번: 다리 만들기 -Python

[백준알고리즘] 2146번: 다리 만들기 -Python

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

2146번: 다리 만들기

와;;; 너무 어려웠다 ㅠㅠㅠ 문제를 푸는 방법은 그래도 찾았는데.. 계속 메모리 초과가 발생했었다.... 큐에 중복 값을 안 넣도록 체크도 했는데.... 그래서 다른 사람들의 코드도 봤는데 내가 푼 방식과 별 다를 바가 없어 보여서 더 헤매었다...

 

그래서 별로 맘에 안 들지만 어찌어찌 다른 방법으로라도 해결을 했고, 다시 마음을 비우고 같은 방법으로 해서 겨우 풀게 되었다. 사실 첫 번째 방법은 보지 않아도 될 정도로 꾸역꾸역 푼 코드라..

 

참고로 이전에 계속해서 BFS로 문제를 풀 때 꺼낸 후에 좌표 범위 검사를 진행했었느나 중복 값이 많이 나와서 원래는 큐에 넣기 전에 확인을 해야 한다. 이번 문제를 풀 때는 메모리 문제 때문에 이 부분도 신경을 써주었다..

 

1. 첫 번째 방법

첫 번째 통과한 코드는 진짜 통과하기 위해서 꾸역꾸역 만들었다. 문제를 해결하는 방식은 아래의 순서와 같다.

 

1. 섬을 BFS로 찾아가면서 grouping

2. 하나의 섬마다 번갈아 가면서 다른 섬들과의 최소 거리를 각각 구하기

 

이 방법이 마음에 들지 않았던 것은 2번 방법 때문이다. 섬의 개수가 많다면 그만큼 반복을 많이 해야 하기 때문에 별로 좋은 방법이라 생각하지 않았었다.

 

이 방법으로 해결하기 위해서 리스트 visited를 추가로 사용해서 섬을 구분해서 grouping을 했는데 지금 봐도 저걸 왜 사용했는지 모르겠다. 그다음 각 섬의 가장자리 바다지역의 좌표를 ocean이라는 딕셔너리에 group_id를 key로 갖는 리스트에 추가해주었다.

 

이 추가한 각 섬들의 바닷가 지역의 좌표를 이용해서 하나의 섬씩 번갈아가면서 다른 섬에 닿는 최소 거리를 구해주었다. 여기서 거리를 계산하기 위해 입력된 지도와 동일한 크기의 NxN 크기의 이중 리스트를 또 생성해서 섬에서부터 1씩 멀어지면서 거리를 측정했다.

 

푸는 방식도 별로 마음에 들지 않기도 했고, 내가 푼 코드를 보는데도 별로 마음에 들지 않는다.

import sys
from collections import deque

def grouping(i, j):
    global visited, world, ocean
    visited[i][j] = True
    world[i][j] = group_id
    ocean[group_id] = []
    q = deque([(i, j)])

    while q:
        qi, qj = q.popleft()
        for i in range(4):
            x, y = qi+dx[i], qj+dy[i]
            if x < 0 or x >= n or y < 0 or y >= n:
                continue
            if world[x][y] == 1 and not visited[x][y]:
                visited[x][y] = True
                world[x][y] = group_id
                q.append((x, y))
            elif not world[x][y]:
                ocean[group_id].append((x, y))

def find_distance(gid):
    q = deque(ocean[gid])
    dist = [[-1]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if world[i][j] == gid:
                dist[i][j] = 0
    for i, j in q:
        dist[i][j] = 1

    while q:
        qi, qj = q.popleft()
        for i in range(4):
            x, y = qi+dx[i], qj+dy[i]
            if x < 0 or x >= n or y < 0 or y >= n:
                continue
            if not world[x][y] and dist[x][y] == -1:
                dist[x][y] = dist[qi][qj] + 1
                q.append((x, y))
            elif world[x][y] and world[x][y] != gid:
                return dist[qi][qj]

n = int(sys.stdin.readline())
world = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
visited = [[False]*n for _ in range(n)]
ocean = {}
dx, dy = (0, 0, -1, 1), (-1, 1, 0, 0)

group_id = 1
for i in range(n):
    for j in range(n):
        if world[i][j] == 1 and not visited[i][j]:
            grouping(i, j)
            group_id += 1

ans = []
for i in range(1, group_id-1):
    ans.append(find_distance(i))

sys.stdout.write(str(0) if len(ans) == 0 else str(min(ans)))

 

2. 두 번째 방식

두 번째 방식은 흔히들 말하는 "간척사업"방식이다. 마음을 비우고 하니까 통과해따;;

 

여기서는 NxN 크기의 이중 리스트가 한 개만 존재한다. 대신 group의 id를 음수 값으로 지정해주어서 처음 입력의 섬과 grouping 된 섬과 구분해주었다.

 

grouping을 해주면서 각 그룹마다 바닷가와 맞닿은 섬의 좌표를 ocean이라는 큐에 넣어주었다. 위의 코드와 달라진 점은 바닷가 지역이 아닌 섬의 지역을 추가한 점과 ocean을 딕셔너리로 섬마다 구분시킨 것이 아닌 모든 좌표를 구분 없이 순서대로 넣었다는 것이다.

 

이후 거리를 구해주는데, 바닷가 지역부터 주변의 바다 쪽으로 영역을 넓혀나갔다. 이때 넓혀간 바다의 좌표는 각 섬의 그룹 번호로 넓혀나갔다. 여기까지의 아이디어를 바탕으로 아래의 예제를 살펴보겠다.

 

<입력>

1 0 0 0 1

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

1 1 0 0 1

 

<grouping 이후>

-1  0 0 0 -2

 0  0 0 0  0

 0  0 0 0  0

 0  0 0 0  0

-3 -3 0 0 -4

 

<한번 간척사업>

-1 -1  0 -2 -2

-1  0  0  0 -2

 0  0  0  0  0

-3 -3  0  0 -4

-3 -3 -3 -4 -4

 

여기서 이제 거리를 구해주기 위해서 몇 번의 간척사업이 이루어지는지 카운트를 했다. 내가 생각한 아이디어는 현재 넓히는 과정에서 이동하려는 위치의 값이 바다가 아니고 땅이라면 거리를 측정한다는 것이다. 여기서 두 가지 경우가 있을 수 있다. 이동하려는 좌표의 그룹번호가 현재 그룹번호보다 낮은 경우 또는 높은 경우이다.

 

낮은 경우라면 아래와 같은 경우이다.

    -1  0  0 -2

-> -1 -1  0 -2

-> -1 -1 -2 -2

-> -1 -1 -2 -2

             -1

이 경우라면 모든 땅이 한 번씩 간척사업을 한 후에 이미 다리가 연결된 것이다. 하지만 이 경우를 두 번째 간척사업을 진행하던 도중 알게 된 것이다. 즉, 현재 간척사업 횟수는 2이지만 1일 때 이미 결정된 것이기 때문에 i번째 간척사업 중이라면 (i-1)*2 의 길이의 다리가 형성되게 된다.

 

반대로 높은 경우라면 아래와 같은 경우이다.

    -1  0  0  0 -2

-> -1 -1  0  0 -2

-> -1 -1  0 -2 -2

-> -1 -1 -1 -2 -2

-> -1 -1 -1 -2 -2

             -2

이 경우는 각자 두 번씩 간척사업을 하려는 도중에 다리가 연결된 경우이다. 그러나 중복된 곳에 간척을 하려고 했기 때문에 1개의 블록이 중복된다. 즉, i번째 간척사업 중에 중복된 곳에 다리를 놓게 되기 때문에 i*2-1 의 길이의 다리가 형성된다.

 

여기서 한 가지 조심해야 하는 점은 처음에 주어졌던 예제의 경우이다. 질문 게시판에서 찾은 예제인데 이 예제의 경우 최소 다리의 길이는 2가 되어야 한다. 1번째 간척사업 때 이미 다리가 형성되지만 이 사실을 2번째 간척사업 단계에서 확인하게 된다. 하지만 2번째 간척사업 때에는 이미 형성된 길이가 2인 다리보다 길이가 3인 다리를 먼저 찾게 될 수 있다. 따라서 간척사업을 진행할 때에는 최소의 다리 길이를 유지하도록 해야 한다.

1 0 0 0 1

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

1 1 0 0 1

import sys
from collections import deque

def grouping(i, j): # 섬마다 번호 붙이기
    q = deque([(i, j)])
    world[i][j] = gid
    while q:
        qi, qj = q.popleft()
        for t in range(4):
            x, y = qi + dx[t], qj + dy[t]
            if 0 <= x < n and 0 <= y < n:
                if world[x][y] == 1:
                    world[x][y] = gid
                    q.append((x, y))
                elif world[x][y] == 0 and not (qi, qj) in ocean:
                    ocean.append((qi, qj))

def get_distance(): # 모든 섬에서 동시에 확장
    loop = 0
    ans = sys.maxsize
    while ocean:
        loop += 1
        length = len(ocean)
        for _ in range(length):
            oi, oj = ocean.popleft()
            for t in range(4):
                x, y = oi + dx[t], oj + dy[t]
                if 0 <= x < n and 0 <= y < n:
                    if world[x][y] == 0:
                        world[x][y] = world[oi][oj]
                        ocean.append((x, y))
                    elif world[x][y] < world[oi][oj]:
                        ans = min(ans, (loop - 1) * 2)
                    elif world[x][y] > world[oi][oj]:
                        ans = min(ans, loop * 2 - 1)
    return ans

dx, dy = (0, 0, 1, -1), (1, -1, 0, 0)
n = int(sys.stdin.readline())
world = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
ocean = deque()
gid = -1

for i in range(n):
    for j in range(n):
        if world[i][j] > 0:
            grouping(i, j)
            gid -= 1

sys.stdout.write(str(get_distance()))

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다