[ 그래프 이론 - 4963 ] 섬의 개수(Python)

---

접근법

기존의 dfs에서 대각선을 탐색하는 경우의 수를 추가해 줘야 하며, "0 0"을 입력받기 전까지 반복해야 함으로 반복할 때 마다 전체 그래프와 cnt를 초기화 해 줘야 한다. 따라서 dfs()의 parameter에 전체 그래프도 추가되어야 한다.

---

정답

import sys
sys.setrecursionlimit(10**6)

di = [0,0,-1,1,1,1,-1,-1]
dj = [1,-1,0,0,1,-1,1,-1]

def dfs(i, j, Map):
    
    Map[i][j] = 0
    
    for k in range(8):
        I = i+di[k]
        J = j+dj[k]
        if 0 <= I < h and 0 <= J < w:
            if Map[I][J] ==1:
                dfs(I,J,Map)

while(True):

    w, h = map(int,sys.stdin.readline().split())
    if w == 0 and h == 0:
        break
    
    Map = []
    cnt = 0
    
    for _ in range(h):
        Map.append(list(map(int,sys.stdin.readline().split(" "))))

    for i in range(h):
        for j in range(w):
            if Map[i][j] == 1:
                cnt+=1
                dfs(i,j,Map)

    print(cnt)

 

di와 dj에서 그래프 특정 노드에서 움직이는 방향을 대각선 요소도 추가해 줌으로써 경우의 수가 8가지가 된다. 따라서 dfs() 내에서 각 경우마다 유효한 이동범위 내에서 섬인지 바다인지를 방문 여부를 통해 확인한다.

 

이전에는 노드간의 연결이였지만, 이번에는 노드간의 연결이라기 보다는 모든 그래프의 위치가 연결되어 있고 1인 경우가 땅이기 때문에 방문여부를 1인지 아닌지로 구분 해 준다면 유사하게 해결할 수 있다.