[Python] DFS - 음료수 얼려 먹기
<문제> 음료수 얼려 먹기
입력 조건
- 첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어집니다.(1 <= N, M <= 1000)
- 두 번째 줄부터 N+1번째 줄까지 얼음 틀의 형태가 주어집니다.
- 이때 구멍이 뚫려있는 부분은 0, 그렇지 않은 부분은 1입니다.
출력 조건
- 한 번에 만들 수 있는 아이스크림의 개수를 출력합니다.
입력 예시
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤ출력 예시
4 5ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤ3
00110
00011
11111
00000
<해결> DFS 활용
- 특정한 지점의 주변 상,하,좌,우를 살펴본 뒤에 주변 지점 중에서 값이 0이면서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문합니다.
- 방문한 지점에서 다시 상,하,좌,우를 살펴보면서 방문을 진행하는 과정을 반복하면, 연결된 모든 지점을 방문할 수 있습니다.
- 모든 노드에 대하여 1~2번 과정을 반복하며, 방문하지 않은 지점의 수를 카운트합니다.
def dfs(x,y):
# 주어진 범위를 벗어나는 경우에는 즉시 종료
if x <= -1 or x >= n or y <= -1 or y >= m:
return False
# 현재 노드를 아직 방문하지 않았다면
if graph[x][y] == 0:
# 해당 노트를 방문 처리
graph[x][y] = 1
# 상,하,좌,우의 위치들도 모두 재귀적으로 호출
dfs(x-1,y)
dfs(x,y-1)
dfs(x+1,y)
dfs(x,y+1)
return True
return False
# N,M을 공백을 기준으로 구분하여 입력 받기
n, m = map(int,input().split())
# 2차원 리스트의 맵 정보 입력 받기
graph = []
# [[0, 0, 1, 1, 0], [0, 0, 0, 1, 1], [1, 1, 1, 1, 1], [0, 0, 0, 0, 0]]
for i in range(n):
graph.append(list(map(int,input())))
# 모든 노드(위치)에 대하여 음료수 채우기
result = 0
for i in range(n):
for j in range(m):
# 현재 위치에서 DFS수행
if dfs(i,j) == True:
result += 1
print(result)
출처
이것이 취업을 위한 코딩테스트다 with 파이썬 (https://youtu.be/PqzyFDUnbrY)
https://covenant.tistory.com/132
Author And Source
이 문제에 관하여([Python] DFS - 음료수 얼려 먹기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@sugenius77/Python-DFS-음료수-얼려-먹기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)