https://www.acmicpc.net/problem/2146
시간 2초, 메모리 192MB
input :
- N(1 <= N <= 100)
- N개의 숫자(0은 바다, 1은 육지)
output :
- 가장 짧은 다리의 길이를 출력
조건 :
- 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서남북으로 육지가 붙어있는 덩어리를 말한다
처음 접근 할 때
BFS로 우선 섬에 순서를 매기자.
2, 3, 4 .....
그 후, 섬의 테두리 부분을 큐에 넣은 후에.
BFS를 수행해서 가장 먼저 다른 섬에 닿으면 break 걸고 출력하자..
queue 가 끝도 없이 늘어나서 인지 메모리가 초과 되었음. 쿸쿠...
다른 분들의 풀이를 보며 개선해야 할 점들 찾기.
- 섬의 테두리 부분을 큐에 넣을 때. 또다른 반복을 하지 않고 그룹핑 할 때 분류 하자.
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)
