[Algorithm] 백준 4963 - 섬의 개수 in Python(파이썬)

💡 백준 4963:

DFS 탐색

🌱 코드 in Python

알고리즘: DFS

import sys

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

dx = [0, 1, 1, 1, 0, -1, -1, -1] # 대각선을 포함한 8방위
dy = [1, 1, 0, -1, -1, -1, 0, 1]

def dfs(cx, cy):
	g[cx][cy] = 0 # 방문 처리
	for x, y in zip(dx, dy):
		nx = cx + x
		ny = cy + y
		if 0 <= nx < h and 0 <= ny < w and g[nx][ny]: # 갈 수 있는 칸이고, 그 칸이 섬일 경우
			dfs(nx, ny)

while True:
	w, h = map(int, input(). split())
	if w == 0 and h == 0: # 0, 0이 들어오면 프로그램 종료
		break
	cnt = 0
	g = [list(map(int, input().split())) for _ in range(h)]
	for i in range(h):
		for j in range(w):
			if g[i][j]: # 섬일 경우
				dfs(i, j) # dfs탐색
				cnt += 1 # dfs탐색 한 텀마다 cnt 1 증가
	print(cnt)

이번 문제 역시 dfs의 standard형 문제여서 푸는 방법에 있어 다른 점은 많지 않았다

그러나 주의해야 할 점은 몇가지 있었는데,
입력 횟수가 주어지지 않으므로 무한루프를 돌다가 0, 0 이 들어올 때 반복문이 종료될 수 있도록 해야 한다

또한, 나와 같이 입력받은 그래프 자체를 방문배열로 사용할 경우
섬이 1이고 바다가 0으로 1일 때 지나갈 수 있다는 것을 명심명심팝팝 해야 한다
여느때와 같이 not [i][j] 요딴 식으로 풀면 큰 코 다친다 ㅎㅎ

마지막으로 대각선도 방문할 수 있으므로 그도 포함해 주어야 한다

🧠 기억하자

1. g = [list(map(int, input().split())) for _ in range(h)]
   • 이런 식으로도 배열을 받을 수 있다!
2. 재귀 제한을 그냥 일단 풀고 시작하는데 depth에 대한 고찰이 필요할지.. 생각 필요..

백준 11724 바로가기