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)