8. DFS로 푼 그래프 문제 (백준 4963 파이썬)

정말 그래프 문제는 아마도 푸는 방법이 다양한 것 같은데 일단 DFS로 풀었다. 반복되는 걸 느끼는 순간 재귀 못놓아.. 그래서 이번에도 필연적으로 또 Recursion Error만났죠.. 하지만 생각해보니 BFS도 재귀하면 되는걸.. 다음에는 시도해보는걸로..

 

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

4963번: 섬의 개수

문제

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

한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 

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

---

일단 그래프니까 dx, dy 만드는데, 대각선으로도 연결 가능해서 8방향으로 해줘야 함

방문한 섬 체크하되, 어차피 섬만 보면 되니까 섬만 체크했다. 

전체를 함수로 넣을까 했는데 처음에 함수로 안만들고 시작하기도 했고, 전체 탐색 부분만 빼도 될 것 같아서 아래의 코드처럼 완성됐다.

import sys
sys.setrecursionlimit(15000)

# 상우하좌
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, 1, 1, 1, 0, -1, -1, -1]


def search(able):
    # 섬 전체 탐색
    for k in range(8):
        next_x = j + dx[k]
        next_y = i + dy[k]

        while 0 <= next_x < h and 0 <= next_y < w and visited[next_x][next_y] == 0 and M[next_x][next_y] == 1:
            visited[next_x][next_y] = 1
            search(next_x, next_y)
    return


while True:
    w, h = map(int, sys.stdin.readline().split())

    # 입력 종료조건
    if w==0 and h==0:
        break

    M = []
    for _ in range(h):
        M.append(list(map(int, sys.stdin.readline().split())))
    visited = [[0]*w for _ in range(h)]
    count = 0
    for i in range(w):
        for j in range(h):
            # 안가본 섬을 발견하면 섬 count
            if M[j][i] == 1:
                if visited[j][i] == 0:
                    visited[j][i] = 1
                    count += 1
                    search(j, i)
    print(count)

• width, height 와 행과 열(i, j) 관계에 대해서 헷갈림.. w가 결국 열 개수라는 것을... 직접 그려봐도 헷갈림..
• 재귀 RecursionError 그만 만나고 싶다 ^^ 이건 그래도 테케는 다 무난하게 돌아가길래 혹시? 하고 setrecursionlimit을 올려봤더니 무사히 통과!!