import sys
from collections import deque
def input():
return sys.stdin.readline().rstrip()
def island_bfs(x,y):
queue = deque()
queue.append((x,y))
visited[x][y] = True
island_check[x][y] = island_cnt
temp = [(x,y)]
while queue:
x,y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<=nx<N and 0<=ny<N:
if not visited[nx][ny] and arr[nx][ny]:
visited[nx][ny] = True
island_check[nx][ny] = island_cnt
queue.append((nx,ny))
temp.append((nx,ny))
island_list.append(temp)
N = int(input())
arr = [list(map(int,input().split())) for _ in range(N)]
visited = [[False for _ in range(N)] for _ in range(N)]
island_list = []
island_check = [[0 for _ in range(N)] for _ in range(N)]
island_cnt = 1
dx = [-1,0,1,0]
dy = [0,-1,0,1]
for x in range(N):
for y in range(N):
if arr[x][y] and not visited[x][y]:
island_bfs(x,y)
island_cnt += 1
result = float('inf')
for island_num in range(len(island_list)):
queue = deque(island_list[island_num])
visited = [[0 for _ in range(N)] for _ in range(N)]
dis = 1
while queue:
q_size = len(queue)
flag = False
for _ in range(q_size):
x,y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<=nx<N and 0<=ny<N:
if island_check[nx][ny] != island_num+1 and not visited[nx][ny]:
visited[nx][ny] = dis
queue.append((nx,ny))
if island_check[nx][ny]:
result = min(result,dis-1)
flag = True
break
if flag:
break
if flag:
break
dis += 1
print(result)가장 첫 풀이는 직관적으로 푼 방식으로 각 섬들을 번호를 마킹해주고,
한 섬의 있는 위치에서 다른 섬에 도착하는 최단 거리를 구해주는 방식이다.
import sys
from collections import deque
def input():
return sys.stdin.readline().rstrip()
def island_bfs(x,y):
queue = deque()
queue.append((x,y))
visited[x][y] = True
island_check[x][y] = island_cnt
temp = [(x,y)]
while queue:
x,y = queue.popleft()
bridge_queue.append((x,y,island_cnt,0))
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<=nx<N and 0<=ny<N:
if not visited[nx][ny] and arr[nx][ny]:
visited[nx][ny] = True
island_check[nx][ny] = island_cnt
queue.append((nx,ny))
temp.append((nx,ny))
island_list.append(temp)
def bfs():
global result
while bridge_queue:
x,y,island_num,dis = bridge_queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<=nx<N and 0<=ny<N:
if island_check[nx][ny] == island_num:
continue
if result <= distance_list[nx][ny]:
return
if not distance_list[nx][ny]:
distance_list[nx][ny] = dis + 1
island_check[nx][ny] = island_num
bridge_queue.append((nx,ny,island_num,dis+1))
else:
if result > distance_list[nx][ny] + distance_list[x][y]:
result = distance_list[nx][ny] + distance_list[x][y]
N = int(input())
arr = [list(map(int,input().split())) for _ in range(N)]
visited = [[False for _ in range(N)] for _ in range(N)]
island_list = []
island_check = [[0 for _ in range(N)] for _ in range(N)]
island_cnt = 1
dx = [-1,0,1,0]
dy = [0,-1,0,1]
bridge_queue = deque()
for x in range(N):
for y in range(N):
if arr[x][y] and not visited[x][y]:
island_bfs(x,y)
island_cnt += 1
result = float('inf')
distance_list = [[0 for _ in range(N)] for _ in range(N)]
bfs()
print(result)이 방식은 좀 더 빨리 풀 수 잇는 방식으로 위에서는 1섬마다 전부 초기화를 하고, 매번 구하는것에 반해
이 방식은 모든 섬에서 bfs를 동시에 시작하는 것이다.
만약 초기 상태의 점을 방문하게 되면, 해당 위치까지의 거리를 distance_list에 넣어주고, island_check에 해당 위치가 어느 섬에서 왔는지 마킹을 해준다.
그리고 만약 초기화 된 값이 아닌 이미 있는 값이라면, 비교를 해서 현재 위치의 distance_list[x][y] 와 distance_list[nx][ny]를 더한 값이 더 작으면 갱신을 해준다.
그리고 result가 distance_list[nx][ny]보다 작을 시에는 더 갱신할 경우의 수가 없으므로 함수를 종료해준다.
'알고리즘 > 백준' 카테고리의 다른 글
| [BOJ/백준] 23289 온풍기 안녕! (0) | 2021.10.25 |
|---|---|
| [BOJ/백준] 1958 LCS 3 (0) | 2021.09.28 |
| [BOJ/백준] 1943 동전 분배 (0) | 2021.09.03 |
| [BOJ/백준] 2143 두 배열의 합 (0) | 2021.09.03 |
| [BOJ/백준] 1823 수확 (0) | 2021.09.03 |