[Python][문제풀이] 음료수 얼려 먹기
🚀 문제
📝풀이
dfs또는 bfs알고리즘을 통해서 모든 지점의 연결된 노드들을 재귀적으로 탐색해서
dfs가 실행된 횟수가 얼음 갯수.
# N, M을 공백으로 구분하여 입력받기
n, m = map(int, input().split())
# 2차원 리스트의 맵 정보 입력받기
graph = []
for i in range(n):
graph.append(list(map(int, input())))
# DFS로 특정한 노드를 방문한 뒤에 연결된 모든 노드들도 방문
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
# 모든 노드에 대하여 음료수 채우기
result = 0
for i in range(n):
for j in range(m):
# 현재 위치에서 DFS 수행
if dfs(i, j) == True:
result += 1
print(result)
dfs또는 bfs알고리즘을 통해서 모든 지점의 연결된 노드들을 재귀적으로 탐색해서
dfs가 실행된 횟수가 얼음 갯수.# N, M을 공백으로 구분하여 입력받기 n, m = map(int, input().split()) # 2차원 리스트의 맵 정보 입력받기 graph = [] for i in range(n): graph.append(list(map(int, input()))) # DFS로 특정한 노드를 방문한 뒤에 연결된 모든 노드들도 방문 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 # 모든 노드에 대하여 음료수 채우기 result = 0 for i in range(n): for j in range(m): # 현재 위치에서 DFS 수행 if dfs(i, j) == True: result += 1 print(result)
문제출처 : 이것이 취업을 위한 코딩테스트다 (저자 나동빈)
Author And Source
이 문제에 관하여([Python][문제풀이] 음료수 얼려 먹기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@youngcheon/Python문제풀이-음료수-얼려-먹기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)