DFS with Python

💡문제설명

문제 : https://www.acmicpc.net/problem/4963

• 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

• 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다.
• 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

입력

• 입력은 여러 개의 테스트 케이스로 이루어져 있다.
• 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다.
• w와 h는 50보다 작거나 같은 양의 정수이다.
• 둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.
• 입력의 마지막 줄에는 0이 두 개 주어진다.

출력

• 각 테스트 케이스에 대해서, 섬의 개수를 출력한다.

❓DFS에 대해

• Depth-First Search, 깊이 우선 탐색이라고도 불립니다.
• 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘입니다.

• 
• DFS 알고리즘 탐색입니다.
• 
• BFS 알고리즘 탐색입니다.

동작과정

• 1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 합니다.
• 2 - 1. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문처리를 합니다.
• 2 - 2. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냅니다.
• 2 번 과정을 더 이상 수행할 수 없을 때까지 반복합니다.

🧑‍💻 코드 풀이

DFS

def dfs(x, y):
    if x == m or y == n:
        return board

    for i in range(8):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < m and 0 <= ny < n and board[nx][ny] == 1:
            board[nx][ny] = 0
            dfs(nx, ny)

solution

while (True):
    n, m = map(int, sys.stdin.readline().split())
    if n == 0 and m == 0:
        break

    board = []
    answer = 0
    for i in range(m):
        board.append(list(map(int, sys.stdin.readline().split())))

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

    print(answer)

전체 코드

import sys
sys.setrecursionlimit(10000)
dx = [0, 1, 1, 1, 0, -1, -1, -1]
dy = [1, 1, 0, -1, -1, -1, 0, 1]

board = []

def dfs(x, y):
    if x == m or y == n:
        return board

    for i in range(8):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < m and 0 <= ny < n and board[nx][ny] == 1:
            board[nx][ny] = 0
            dfs(nx, ny)

while (True):
    n, m = map(int, sys.stdin.readline().split())
    if n == 0 and m == 0:
        break

    board = []
    answer = 0
    for i in range(m):
        board.append(list(map(int, sys.stdin.readline().split())))

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

    print(answer)