- 7주차 과제 - 섬 간 이동(dfs / bfs)
-
사용 언어 : python
-
해결 날짜 : 2021-04-26
-
느낀점 및 해결 과정 :
- dfs 함수를 통해 각각의 섬에 번호를 붙여서 초기화를 해준다. (1번 섬은 전부 -1로, 2번 섬은 전부 -2로 등)
-
bfs 함수를 통해 각 섬에서 다른 섬으로의 최단 거리를 찾는다. 이 때 방향 벡터를 사용하여 상, 하, 좌, 우 로의 다음 위치 값을 비교하여 다음 위치가 주어진 범위를 벗어나는 경우 continue, 다음 위치도 현재 섬일 때 섬에서 방문하지 않았던 부분이라면 방문 처리 후 queue에 추가, 다음 위치가 바다인 경우는 거리를 표시해 주고 queue에 추가, 다른 섬을 만난 경우 거리를 계산하여 작은 값으로 교체 후 bfs를 종료하는 방법으로 문제를 해결하였다.
-
시간 복잡도 :
- dfs : O(N2)
- bfs : 섬의 개수만큼 bfs를 호출, 함수 내부에서는 인접 행렬이므로 O(N2)
- 따라서 O(N2 + K*N2) = O(N2) 의 시간 복잡도를 갖는다.
- 코드
from collections import deque import copy # 각 섬의 값을 순서대로 -1, -2 , -3... 넘버링 def dfs(x, y): global island_number # 주어진 범위를 벗어나는 경우 종료 if x < 0 or x >= N or y < 0 or y >= N: return False # 방문하지 않은 노드 중 섬인 노드 if island[x][y] == 1 and visited[x][y] == 0: # 섬의 첫 방문인 경우 좌표 값을 queue에 추가해줌 if len(island_info) < island_number: island_info.append((x, y)) visited[x][y] = 1 island[x][y] = -island_number dfs(x - 1, y) dfs(x, y - 1) dfs(x + 1, y) dfs(x, y + 1) return True return False def bfs(a, b): global answer visited_island = [[0] * N for _ in range(N)] # 깊은 복사를 통해 섬마다 bfs 할 때 마다 섬의 거리가 초기화 island_copy = copy.deepcopy(island) queue = deque() queue.append((a, b)) while queue: x, y = queue.popleft() visited_island[x][y] = 1 for idx in range(4): nx = x + dx[idx] ny = y + dy[idx] # 다음 위치가 주어진 범위를 벗어나는 경우 if nx < 0 or nx >= N or ny < 0 or ny >= N: continue # 다음 위치도 현재 섬인 경우 if island_copy[nx][ny] == island_copy[a][b]: # 섬에서 방문하지 않은 부분인 경우 if visited_island[nx][ny] == 0: visited_island[nx][ny] = 1 queue.append((nx, ny)) continue # 다음 위치가 바다인 경우 if island_copy[nx][ny] == 0: # 현재 위치가 섬이라면 음수이므로 거리는 1로 초기화 if island_copy[x][y] < 0: island_copy[nx][ny] = 1 elif island_copy[x][y] > 0: island_copy[nx][ny] = island_copy[x][y] + 1 queue.append((nx, ny)) # 다른 섬을 만난 경우 if island_copy[nx][ny] < 0: temp = island_copy[x][y] # 작은 값으로 교체 answer = min(answer, temp) return # 섬 초기화 N = int(input()) island = [list(map(int, input().split())) for _ in range(N)] visited = [[0] * N for _ in range(N)] # 방향벡터 R, D, L, U dx = [0, 1, 0, -1] dy = [1, 0, -1, 0] # 각 섬을 bfs하기 위한 queue island_info = deque() island_number = 1 # 섬이 대각선으로 있는 경우의 최대 값 answer = 2 * N - 3 # dfs를 통해 섬 넘버링 for i in range(N): for j in range(N): # 한 섬을 완료하면 다른 섬에는 다른 번호를 붙여줌 if dfs(i, j): island_number += 1 # bfs를 통해 최단 거리 찾기 while island_info: popped = island_info.popleft() bfs(popped[0], popped[1]) print(answer)