문제
https://school.programmers.co.kr/learn/courses/30/lessons/154540
각 무인도의 식량 합계를 리스트로 나타내는 문제
이차원 배열을 읽어야 하며, 어느 점들이 어떤 무인도에 속한 점인지를 파악할 수 있어야 한다
전략
01. DFS
X가 아닌 어떤 한 무인도의 점을 찾았다면 그 주변의 모든 이어지는 점을 연달아 찾아서 더해주면 한 무인도의 전체 식량 개수가 된다. 따라서 DFS로 풀되 재귀로 풀면 될 것 같다.
풀이
import sys
sys.setrecursionlimit(10000)
def dfs(maps, y, x, visited):
visited[y][x] = True
total = int(maps[y][x])
dy = (0, 0, 1, -1)
dx = (1, -1, 0, 0)
for i in range(4):
if 0 <= y + dy[i] < len(maps) and 0 <= x + dx[i] < len(maps[0]) and not visited[y + dy[i]][x + +dx[i]] and maps[y + dy[i]][x + dx[i]] != "X":
total += dfs(maps, y + dy[i], x + dx[i], visited)
return total
def solution(maps):
visited = [[False for _ in range(len(maps[0]))] for _ in range(len(maps))]
answer = []
for y in range(len(maps)):
for x in range(len(maps[0])):
if visited[y][x]:
continue
if maps[y][x] == "X":
visited[y][x] = True
continue
a = dfs(maps, y, x, visited)
answer.append(a)
return sorted(answer) if answer else [-1]
이 문제에서는 조금 많이 헤맸는데, 파이썬의 최대 재귀 횟수 제한으로 인해 계속 런타임 에러가 떴던 것이었다. sys.setrecursionlimit(10000)로 하니까 바로 풀렸다.
visited = [[False for _ in range(len(maps[0]))] for _ in range(len(maps))]
answer = []
먼저 한번 방문한 노드를 재방문해 중복으로 식량 수가 카운트되는 걸 방지하기 위해 맵과 똑같은 크기의 visited 변수를 만들어 체크하도록 했고, 정답을 저장할 answer 리스트를 만들어주었다.
상상했을 때 (0, 0)인 점부터 차례차례 읽어나가면서 X인 점에서는 visited의 해당 요소를 True로 바꿔주다가, X가 아닌 점을 만나면 그 점에서 dfs를 시작해 그 주변의 셀 수 있는 점을 재귀적으로 탐색한다. 위 그림에서 보면 5인 점에서 상하좌우를 살핀다. 1, 9를 셀 수 있는데, 만약 여기서 1을 먼저 탐색했다면 1인 점에서 다시 재귀적으로 dfs를 호출하고 다시 2인 점을 찾고 해서 최종적으로 9인 점까지 탐색하고 난 뒤에 주변에 모든 점이 이동 불가능하거나, X거나, visited이 이미 True이므로 자기 자신의 값을 return해준다.
def dfs(maps, y, x, visited):
visited[y][x] = True
total = int(maps[y][x])
dy = (0, 0, 1, -1)
dx = (1, -1, 0, 0)
for i in range(4):
if 0 <= y + dy[i] < len(maps) and 0 <= x + dx[i] < len(maps[0]) and not visited[y + dy[i]][x + +dx[i]] and maps[y + dy[i]][x + dx[i]] != "X":
total += dfs(maps, y + dy[i], x + dx[i], visited)
return total
위의 설명을 코드로 옮기면 이렇게 된다. 0 <= y + dy[i] < len(maps) and 0 <= x + dx[i] < len(maps[0]) 조건으로 범위를 벗어나는 점은 체크하지 않도록하고, not visited[y + dy[i]][x + +dx[i]] 조건으로 방문하지 않은 점을 찾고, 마지막으로 maps[y + dy[i]][x + dx[i]] != "X" 조건으로 X가 아닌 점을 찾는다. 세가지 조건을 모두 만족하는 점이 해당 점 주변의 셀 수 있는 점이다.
'프로그래밍 > 문제풀이' 카테고리의 다른 글
[코딩테스트] 백준 - 에디터 (0) | 2023.09.20 |
---|---|
[코딩테스트] 2021 Dev-Matching: 웹 백엔드 개발자(상반기)다단계 - 칫솔 판매 (0) | 2023.08.17 |
[코딩테스트] 연습문제 - 124 나라의 숫자 (0) | 2023.08.09 |
[코딩테스트] 연습문제 - 햄버거 만들기 (0) | 2023.08.09 |
[코딩테스트] 연습문제 - 뒤에 있는 큰 수 찾기 (0) | 2023.08.06 |