https://school.programmers.co.kr/learn/courses/30/lessons/154540
기초적인 BFS 문제이다. 별 거 없이 방문여부, 현재 좌표, 최대 길이, 지도 전체 등등 다 넘겨버리면 그만.
BFS 사용 자체가 간만이라 기초 연습문제로 몸풀기.
# bfs 풀이가 필요함
from collections import deque
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
def bfs(maps, i, j, n, m, visit):
queue = deque()
queue.append((i, j))
visit[i][j] = 1
area = int(maps[i][j])
while queue:
x, y = queue.popleft()
for d in range(4):
# 새로운 좌표로 한 칸 이동
nx = x + dx[d]
ny = y + dy[d]
if 0 <= nx < n and 0 <= ny < m:
# 유효한 좌표 범위일 때, 방문 여부와 지도 유효화를 넣는다.
if visit[nx][ny] == 0 and maps[nx][ny] != 'X':
# 방문한 적도 없고, 지도도 숫자가 있으면 원하는 행동을 하고 방문여부를 넣는다.
# 두 번 들틸 필요는 없으니까.
visit[nx][ny] = 1
area += int(maps[nx][ny])
queue.append((nx, ny))
return area
def solution(maps):
# n은 y축 개수, m은 x축 개수로 하자.
n, m = len(maps), len(maps[0])
# 방문 여부를 담아서 방문을 할지 말지를 결정하게 하자.
visit = [[0] * m for _ in range(n)]
answer = []
# 좌표를 순서대로 탐색해서, 방문한 적이 없고, X도 아닐 경우 방문을 시작하자.
for i in range(n):
for j in range(m):
if maps[i][j] != 'X' and visit[i][j] == 0:
#넣을 때 시작좌표랑 전체 판 사이즈랑, 방문 여부랑 지도 전체를 넘겨야함
answer.append(bfs(maps, i, j, n, m, visit))
if len(answer) > 0:
return sorted(answer)
else:
return [-1]
'알고리즘 & PS' 카테고리의 다른 글
[프로그래머스] 시소 짝꿍(Lv 2) (0) | 2023.12.31 |
---|---|
[프로그래머스] 리코쳇 로봇 (Lv 2) (0) | 2023.12.31 |
[프로그래머스] 숫자 변환하기 (Level 2) (0) | 2023.12.26 |
[프로그래머스] Lv 2 2개 이하로 다른 비트 (0) | 2022.01.19 |
[프로그래머스] Lv2 - 튜플 (0) | 2021.10.08 |