7주차 [ 음료수 얼려 먹기 ]

7주차 [ 음료수 얼려 먹기 ]

문제 출처 : 유튜브 동빈나

풀이 요소

인접한 노드 모두 방문해야 한다 -> dfs 활용

입력을 graph화 시키기 & 방문 체크 표현 방법

dfs 진행한 덩어리를 count로 출력

다 돌기 위해 이중 For문 활용

graph에서 상하좌우 이동 어떻게 할 건지 & 벗어나는 경우 생각

풀이

입력 graph로 표현하기

m,n = map(int,input().split()) #가로:m, 세로:n graph=[] #빈 그래프 하나 만들어주고 for _ in range(n): graph.append(list(map(int,input())))

맨 처음에 생각한 건 map으로 안하고 input()으로만 썼다. 하지만 이렇게 하니 우리가 원하는 행렬 방식의 리스트를 만들 수 없었고, 그냥 str 형태로 나타나게 되었다.

list(map(int,input())) 의 효과 : input되는 요소 하나하나씩 int로 처리해준다. 그래서 우리가 원하는 행렬을 만들 수 있다.

dfs 함수 + 상하좌우 이동 처리 방법 + 방문 처리

def dfs(x,y): if x<=-1 or x>=n or y<=-1 or y<=m: #범위를 벗어나면 return False #false를 리턴한다 if graph[x][y] == 0: #범위 안벗어나고 요소가 0이면 graph[x][y] = 1 #1로 바꿔준다 #이게 방문처리 한 거임. 바로 이렇게 1로 바꿔주면서 나중에 1인 거는 pass함 dfs(x-1,y) #상하좌우에 관해 재귀적으로 파고 들어가서 다시 함수 실시해준다. dfs(x+1,y) dfs(x,y-1) dfs(x,y+1) #상하좌우로 연결되어있는 곳을 모두 방문하고 나면 true값이 1번 출력된다 #왜냐면 재귀적으로 들어가서 각각 막히면 안에서 false값을 띄우면서 빠져나오게 되고 #재귀를 다 빠져나오고 가장 바깥에 있는 것은 dfs를 실시했기 때문에 true값을 1번 출력함 return True return False #이도 저도 아닌 (=1인 경우) 경우에는 false값을 출력

이중 for문 + count 출력

count = 0 for i in range(n): for j in range(m): if dfs(j,i) == true: count += 1

전체 코드

#connected component 찾기 n,m = map(int,input().split()) #가로 m 세로 n graph=[] for _ in range(n): graph.append(list(map(int,input()))) count=0 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+1,y) dfs(x,y-1) dfs(x,y+1) return True return False for i in range(n): for j in range(m): if dfs(j,i) == True: count+=1 print(count)

from http://newwave.tistory.com/89 by ccl(A) rewrite - 2021-08-06 16:00:17