BOJ 2146 다리 만들기

LONGNEW·2021년 1월 17일
0

BOJ

목록 보기
62/333
post-thumbnail

https://www.acmicpc.net/problem/2146
시간 2초, 메모리 192MB
input :

  • N(1 <= N <= 100)
  • N개의 숫자(0은 바다, 1은 육지)

output :

  • 가장 짧은 다리의 길이를 출력

조건 :

  • 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서남북으로 육지가 붙어있는 덩어리를 말한다

처음 접근 할 때
BFS로 우선 섬에 순서를 매기자.
2, 3, 4 .....
그 후, 섬의 테두리 부분을 큐에 넣은 후에.
BFS를 수행해서 가장 먼저 다른 섬에 닿으면 break 걸고 출력하자..

queue 가 끝도 없이 늘어나서 인지 메모리가 초과 되었음. 쿸쿠...

다른 분들의 풀이를 보며 개선해야 할 점들 찾기.

  1. 섬의 테두리 부분을 큐에 넣을 때. 또다른 반복을 하지 않고 그룹핑 할 때 분류 하자.
            elif graph[nx][ny] == 0 and not (now_x, now_y, 0) in queue:
                queue.append((now_x, now_y, 0))

(nx, ny) 가 섬의 바깥 즉, 바다일 경우에 현재 존재하는 (now_x, now_y)를 큐에 넣어주고 거리가 0이라는 것을 표시해준다.
in 메소드를 통해 중복이 생기지 않도록 하자.

거리를 구하는 경우

상, 하, 좌, 우를 수행하는 현재의 섬 번호가.


맞 닿는 섬의 번호보다 **작을 때,** **작다는 것**은 무슨 말이냐?

큐에서 나오는 섬의 번호는 순서가 존재 한다.
내가 2, 3, 4 순서대로 큐에 집어넣었다면 다시 큐에서 뺄 때에도 순서를 유지한다.


이미 BFS를 수행해서 2인 섬은 1칸씩 거리를 늘렸다.
여기에 4인 섬이 BFS를 수행하면 4가 들어와야 함 자리에 닿게 되는 데
이 경우에 거리를 구하려면 (cnt + 1) * 2 - 1를 계산 해 주어야 한다.


맞 닿는 섬의 번호보다 클 때.

섬의 번호가 4인 것을 BFS 수행하면 5와 만나게 되는데 이 때는, BFS를 수행하기 전에 이미 만난 것이기에 (cnt) * 2 를 계산해 주어야 한다.

        if graph[nx][ny] == 0:
            graph[nx][ny] = graph[x][y]
            queue.append((nx, ny, cnt + 1))

        elif graph[nx][ny] > graph[x][y]:
            dis = min(dis, cnt * 2)

        elif graph[nx][ny] < graph[x][y]:
            dis = min(dis, ((cnt + 1) * 2) - 1)

이 BFS를 한 라운드 씩.
전체적으로 1번 / 2번 / 나눌 수 있을 거 같아서 불린도 넣었다가 여러 가질 했는데.
결과적으론 이거 때문에 시간을 많이 썼다... 다음 부턴 엑셀을 더 이용 하자 말로만 써놓으니까 너무 이상하다...

import sys
from _collections import deque

n = int(sys.stdin.readline())
graph = []

for i in range(n):
    data = list(map(int, sys.stdin.readline().split()))
    graph.append(data)

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

def BFS(x, y, num):
    q = deque([(x, y)])
    graph[x][y] = num

    while q:
        now_x, now_y = q.popleft()
        for i in range(4):
            nx = now_x + dx[i]
            ny = now_y + dy[i]
            if nx >= n or nx < 0 or ny >= n or ny < 0:
                continue
            if graph[nx][ny] == 1:
                graph[nx][ny] = num
                q.append((nx, ny))
            elif graph[nx][ny] == 0 and not (now_x, now_y, 0) in queue:
                queue.append((now_x, now_y, 0))

cnt = 2
queue = deque()
for i in range(n):
    for j in range(n):
        if graph[i][j] == 1:
            BFS(i, j, cnt)
            cnt += 1

dis = 99999
while queue:
    done = False
    x, y, cnt = queue.popleft()
    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
        if nx >= n or nx < 0 or ny >= n or ny < 0:
            continue

        if graph[nx][ny] == 0:
            graph[nx][ny] = graph[x][y]
            queue.append((nx, ny, cnt + 1))

        elif graph[nx][ny] > graph[x][y]:
            dis = min(dis, cnt * 2)

        elif graph[nx][ny] < graph[x][y]:
            dis = min(dis, ((cnt + 1) * 2) - 1)

print(dis)

0개의 댓글