728x90
반응형
문제:
풀이방법:
숫자를 만난 순간부터 계속해서 숫자를 연속해서 탐지할 수 있도록 알고리즘을 구성해야 하고 따라서 DFS를 사용해서 해당 문제를 풀었다.
maps를 탐색하다가 X가 아니고, 이전에 탐색한 곳이 아니라면 DFS를 수행하며, 연속된 영역을 탐색하는 동안 visited를 계속해서 갱신하도록 한다. 이와 같은 과정을 방문할 곳이 남아 있지 않을 때까지 수행하고, 각 영역의 넓이는 마지막에 정렬을 하도록 한다.(단, 정렬할 영역이 없다면 -1을 반환)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
from collections import deque
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
def dfs(x, y, maps, visited):
area = int(maps[x][y])
queue = deque([(x,y)])
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<=nx<len(maps) and 0<=ny<len(maps[0]):
if maps[nx][ny]!='X' and visited[nx][ny]==0:
area+=int(maps[nx][ny])
visited[nx][ny] = 1
queue.append((nx, ny))
return area, visited
def solution(maps):
visited = [[0 for _ in range(len(maps[0]))] for _ in range(len(maps))]
answers = []
for i in range(len(maps)):
for j in range(len(maps[0])):
if maps[i][j]!='X' and visited[i][j]==0:
visited[i][j] = 1
answer, visited = dfs(i, j, maps, visited)
answers.append(answer)
if len(answers):
return sorted(answers)
else:
return [-1]
|
cs |
문제링크:
https://school.programmers.co.kr/learn/courses/30/lessons/154540
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
728x90
반응형
'Algorithm > Python' 카테고리의 다른 글
| [Programmers]Lv 2. 호텔 대실 (0) | 2023.07.25 |
|---|---|
| [BOJ] 1515. 수 이어 쓰기 (0) | 2023.07.24 |
| [BOJ] 19941. 햄버거 분배 (0) | 2023.07.20 |
| [BOJ] 20920. 영단어 암기는 괴로워 (0) | 2023.07.19 |
| [Programmers] Lv 2. 연속된 부분 수열의 합 (0) | 2023.07.18 |