❓ 문제
프로그래머스 Level 2 연습문제 > 무인도 여행
❗ 해결
전형적인 BFS/DFS 문제이다.
def solution(maps):
H = len(maps)
W = len(maps[0])
island = []
visited = [[False] * W for _ in range(H)]
for i in range(len(maps)):
for j in range(len(maps[0])):
if maps[i][j] != 'X' and visited[i][j] == False:
island.append(bfs(i, j, H, W, maps, visited))
if len(island) == 0:
return [-1]
else:
island.sort()
return island먼저 각 섬마다 머물 수 있는 일수를 저장해줄 island 리스트를 선언한다.
그리고 방문했던 곳을 체크할 visited 리스트를 선언한다.
그리고, 반복문을 돌면서 방문했던 곳이 아니면서, 갈 수 없는곳 ('X') 이 아닌 경우 bfs 함수를 실행한다.
만약 island가 비어있는 경우(갈 곳이 없는 경우) -1을 리스트에 담아 리턴하고, 그렇지 않은 경우 오름차순으로 정렬해서 리턴한다.
그리고 bfs를 구현하기 위한 deque를 import해준 후
bfs 함수를 정의했다.
def bfs(x, y, H, W, maps, visited):
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
queue = deque()
queue.append([x, y])
visited[x][y] = True
answer = int(maps[x][y])
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < H and 0 <= ny < W and visited[nx][ny] == False and maps[nx][ny] != 'X':
answer += int(maps[nx][ny])
visited[nx][ny] = True
queue.append([nx, ny])
return answer상하좌우로 움직일 dx, dy를 선언한 후, deque를 사용해서 풀었다.
이미 방문한 곳이나, 맵을 벗어날 경우, X가 있는 경우를 제외한 곳은 갈 수 있는 곳이므로, 해당 방문한 위치에 존재하는 값을 answer에 누적해준다.
중요한 것은 answer의 초기값은
answer = int(maps[x][y]) 가장 맨 처음 방문한 곳부터 시작해야 하므로 0으로 초기화하면 안된다. (사실 0으로 초기화해서 한참 헤메다가 발견했다..)
<전체소스>
from collections import deque
def bfs(x, y, H, W, maps, visited):
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
queue = deque()
queue.append([x, y])
visited[x][y] = True
answer = int(maps[x][y])
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < H and 0 <= ny < W and visited[nx][ny] == False and maps[nx][ny] != 'X':
answer += int(maps[nx][ny])
visited[nx][ny] = True
queue.append([nx, ny])
return answer
def solution(maps):
H = len(maps)
W = len(maps[0])
island = []
visited = [[False] * W for _ in range(H)]
for i in range(len(maps)):
for j in range(len(maps[0])):
if maps[i][j] != 'X' and visited[i][j] == False:
island.append(bfs(i, j, H, W, maps, visited))
if len(island) == 0:
return [-1]
else:
island.sort()
return island
이 문제는 백준의 유기농 배추(1012)나 미로탐색(2178), 단지번호붙이기(2667)이랑 매우 비슷했다.
