4963번: 섬의 개수

 

 

 

 

풀이

 

dfs 와 bfs로 풀 수 있는 문제입니다.

 

 

 

dfs

...

아직 방문하지 않은 graph[i][j]가 1인곳에서 dfs을 호출하고 graph[x][y] = 0 으로 방문처리 해줍니다.

 

상,하,좌,우 그리고 대각선에 대한 다음위치를 특정해주고 graph[nx][ny] == 1 이라면 dfs를 재호출 합니다.

 

주위에 1이 없다면 섬이 연결돼있는 부분을 다 탐색한것이므로 cnt를 1 증가 시켜줍니다. 

...

 

 

bfs

...

아직 방문하지 않은 graph[i][j]가 1인곳에서 bfs을 호출하고 graph[x][y] = 0 으로 방문처리 해줍니다.

 

상,하,좌,우 그리고 대각선에 대한 다음위치를 특정해주고 graph[nx][ny] == 1 이라면 queue에 nx, ny를 삽입하고 graph[i][j] = 0 으로 방문 처리합니다.

 

quque가 비게 된다면 섬이 연결돼있는 부분을 다 탐색한것이므로 cnt를 1 증가 시켜줍니다. 

...

 

 

 

 

파이썬 dfs

from io import StringIO
import sys
sys.setrecursionlimit(1000000)


def dfs(x, y):   
    dx = [-1, 1, 0, 0, -1, -1, 1, 1]
    dy = [0, 0, -1, 1, -1, 1, -1, 1]
    graph[x][y] = 0

    for i in range(8):
        nx = x + dx[i]
        ny = y + dy[i]

        if (0 <= nx < h) and (0 <= ny < w) and graph[nx][ny] == 1:                    
            dfs(nx, ny)

out = StringIO()
while True:
    w, h = map(int, input().split())

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

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

    out.write(str(cnt)+"\n")
print(out.getvalue().rstrip())

 

 

 

 

 

파이썬 bfs

from collections import deque
from io import StringIO
import sys


def bfs(x, y):   
    dx = [-1, 1, 0, 0, -1, -1, 1, 1]
    dy = [0, 0, -1, 1, -1, 1, -1, 1]
  
    queue = deque()
    queue.append((x, y))
    graph[x][y] = 0

    while queue:
        x, y = queue.popleft()

        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]

            if (0 <= nx < h) and (0 <= ny < w) and graph[nx][ny] == 1:        
                queue.append((nx, ny))  
                graph[nx][ny] = 0  

out = StringIO()
while True:
    w, h = map(int, input().split())

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

    cnt = 0
    for i in range(h):
        for j in range(w):
            if graph[i][j] == 1:
                bfs(i, j)
                cnt += 1

    out.write(str(cnt)+"\n")
print(out.getvalue().rstrip())