[ 문제 ]

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

[ 알고리즘 유형 ]

그래프 이론
그래프 탐색
너비 우선 탐색
깊이 우선 탐색

[ 정답 코드 ]

BFS

# BFS
from collections import deque
import sys
input = lambda:sys.stdin.readline()

dx = [-1,1,0,0,-1,-1,1,1]
dy = [0,0,-1,1,-1,1,-1,1]

def bfs(x, y, cnt):
    q = deque()
    q.append((x,y))
    visited[x][y] = cnt
    while q:
        x,y = q.popleft()
        for k in range(8):
            nx = x+dx[k]
            ny = y+dy[k]
            if 0 <= nx < h and 0 <= ny < w:
                if data[nx][ny] == 1 and visited[nx][ny] == 0:
                    q.append((nx,ny))
                    visited[nx][ny] = cnt
    
while True:
    w,h = map(int, input().split())
    if w == 0 and h == 0: break
    
    data = [ list(map(int, input().split())) for _ in range(h)]
    visited = [ [0] * (w) for _ in range(h)]
    cnt = 0
    for i in range(h):
        for j in range(w):
            if data[i][j] == 1 and visited[i][j] == 0: # 섬 && 방문X
                cnt += 1
                bfs(i, j, cnt)
    print(cnt)

[ 풀이 방법 ]

4방향에 대각선까지 확인해봐야하는 문제였다.

dx = [-1,1,0,0,-1,-1,1,1]
dy = [0,0,-1,1,-1,1,-1,1]

visited[i][j] = 1로 방문 체크를 해줘도 되지만
이번에 구현할 때는 그냥 인자값으로 cnt값을 넘기고 cnt값으로 방문체크를 해줬다.

[ 풀이과정 이슈 ]

DFS로 풀었더니 메모리초과 발생 '_'