[이것이 코딩 테스트다 with Python] DFS/BFS - 음료수 얼려먹기 (Python)

이 글은 이것이 취업을 위한 코딩테스트다 책을 기반으로 쓰여진 글입니다.
출처 : 이것이 취업을 위한 코딩테스트다

---

문제

N * M 크기의 얼음틀이 있다. 구멍이 뚫려있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오. 다음의 4 X 5 얼음 틀 예시에서는 아이스크림이 총 3개 생성된다.

00110

00011

11111

00000

입력

• 첫 번째 줄에 얼음 틀의 새로 길이 N과 가로 길이 M이 주어진다.( 1<=N, M <= 1000)
• 두 번째 줄부터 N+1번째 줄까지 얼음 틀의 형태가 주어진다.
• 이때 구멍이 뚫여있는 부분은 0, 그렇지 않은 부분은 1이다.

 출력

• 한 번에 만들 수 있는 아이스크림 개수를 출력한다.

---

 

알고리즘

1. DFS 함수 정의 

- 현재 노드가 주어진 범위를 벗어나는 경우 종료 (Retrun False)

- 현재 노드를 방문 처리하지 않았다면 방문 처리하기

- 현재 노드의 상,하,좌,우 모두 재귀적으로 호출 후 True 반환 (Return True)

- 현재 노드가 방문되어있다면 종료 (Return False)

2. 2차원 리스트 전체에 위치에 대해서 DFS 수행

3. 현재 위치에서 True가 반환되면 answer 1씩 증가

 

 

 

 

내 소스 코드

n,m = map(int,input().split())

graph = [list(map(int,input())) for _ in range(n)]

def dfs(x,y):
    if x < 0 or x > n-1 or y < 0 or y > m-1 :
        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

answer = 0

for i in range(n):
    for j in range(m):
        if dfs(i,j) == True:
            answer += 1

print(answer)

 

결과