[백준] 4963: 섬의 개수

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

 

import sys
sys.setrecursionlimit(10**4)
while True:
    w, h = map(int, sys.stdin.readline().split())
    if w == 0 and h == 0:
        break
    graph = [  ]
    for i in range(h):
        graph.append(list(map(int, sys.stdin.readline().split())))
    visited = [ [0]*w for _ in range(h) ]
    dx = [ 0, 0, -1, 1, 1, 1, -1, -1 ]
    dy = [ -1, 1, 0, 0, 1, -1, -1, 1 ]
    count = 0
    def dfs(x, y):
        visited[x][y] = 1
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < h and 0 <= ny < w:
                if graph[nx][ny] == 1 and not visited[nx][ny]:
                    dfs(nx, ny)
    for i in range(h):
        for j in range(w):
            if graph[i][j] == 1 and not visited[i][j]:
                dfs(i, j)
                count += 1
    print(count)

graph[h][w]입니다. w, h가 입력되지만, (w는 너비, h는 높이) w=5, h=4일 때

   w=0  1  2  3  4   (너비, width)
h=0  [1, 1, 1, 0, 0]
h=1  [1, 1, 0, 0, 0]
h=2  [0, 0, 0, 1, 1]
h=3  [0, 0, 0, 1, 1]

이렇게 되기 때문에 graph[h][w] h= 3, w= 4일때 가장 오른쪽 아래에 있는 1이 됩니다.

그래서 x자리에 h가 들어가고 y자리에 w가 들어갑니다. 우리가 관례적으로 x라는 단어가 첫 번째인자에 들어가고 y가 두 번째 자리에 들어가는 겁니다. 위치이지 의미는 없습니다.

행을 먼저 탐색하고 그 행속에서 열을 탐색해서 원하는 원소를 찾게됩니다. 행을 이루는 것이 h이고, 열을 이루는 것이 너비인 w입니다.