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 |