백준 4963 섬의 개수 파이썬

4963번: 섬의 개수 (acmicpc.net)

import sys

input= sys.stdin.readline
sys.setrecursionlimit(10**6)


def dfs(y, x):
    if x>=0 and y>=0 and x<w and y<h and graph[y][x]==1:
        graph[y][x]=0
        dfs(y+1, x+1)
        dfs(y-1, x-1)
        dfs(y-1, x+1)
        dfs(y+1, x-1)
        dfs(y+1, x)
        dfs(y-1, x)
        dfs(y, x-1)
        dfs(y, x+1)
        return True
    return False

while True: 
    count=0
    w, h = map(int, input().split())
    if w==0 and h==0:
        break
    else:
        graph=[]
        for i in range(h):
            graph.append(list(map(int, input().split())))
        
        for i in range(h):
            for j in range(w):
                if dfs(i, j)==True:
                    count+=1
        print(count)

 

 

기본적인 dfs 문제인데 1. 대각선 연결도 됨  2.입력을 몇 개 받을지 모르고 종료될 때까지 계속 받음 

이라는 점이 특이하다. 

 

주의할 점:

 

그래프에서 높이랑 너비가 있는데 dfs(높이, 너비)라는 것이 조금 헷갈렸다. dfs(x, y)라고 쓰려고 했었는데 그렇게 하려면 인풋을 받을 때부터 높이, 너비 순으로 받든 그래프를 만들 때 그렇게 만들든 x의 정의를 높이로, y의 정의를 너비로 생각해야 하는데 그게 더 헷갈린다. 

 

그래서 그냥 dfs(높이, 너비) 이렇게 생각하면서 y, x로 이해하는 것이 나한테는 제일 편한 것 같다.