[Python] 백준 4963: 섬의 개수

유기농 배추를 비롯한 다른 bfs, dfs 문제와 큰 차이점이 없는 문제. 차이점이라면 탐색을 할 때 사방 탐색으로만 그치지 않고, 8방향으로 탐색을 해주어야 한다는 것이다.

 

 

ANS

from collections import deque
import sys
input = sys.stdin.readline

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

def bfs(ls, x, y):
    q = deque()
    if ls[x][y] == 1:
        q.append((x,y))
        ls[x][y] = 0

        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 ls[nx][ny] == 1:
                        ls[nx][ny] = 0
                        q.append((nx,ny))
        return

while True:
    w,h = map(int, input().split())
    cnt = 0
    if w == 0 and h == 0:
        break
    else:
        ls =[]
        for _ in range(h):
            ls.append(list(map(int,input().split())))
    for r in range(h):
        for c in range(w):
            if ls[r][c] == 1:
                bfs(ls, r, c)
                cnt += 1
    print(cnt)

+

처음에 DFS BFS를 처음 접했을 땐 이걸 어떻게 풀지? 싶은 마음 반과 실제로 안 풀려서,,, 고생을 정말 많이 했는데 차분히 문제들을 풀어본 후 solve 유무를 떠나서 다른 분들의 코드를 참고하니 문제와 코드를 더욱 다각도로 바라볼 수 있게 되고 로직이 탄탄해진 것 같다는 느낌을 많이 받는 중.

남들의 코드를 보고 분석하는 것을 부끄러워하지 않고 접근 방식이 헷갈릴 수록 자주 할 것! 아무래도 차근차근 배울 수 있는 환경이 아닌 만큼 주변의 자원을 잘 이용해야겠다는 생각이 든다.