[구름톤 챌린지] Day 12 - 발전기(DFS)

https://level.goorm.io/exam/195694/%EB%B0%9C%EC%A0%84%EA%B8%B0/quiz/1

구름LEVEL

---

문제

---

풀이

import copy
from collections import deque

n = int(input())

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

arr = [list(map(int,input().split())) for _ in range(n)]
visited = copy.deepcopy(arr)

dq = deque()
cnt = 0

for i in range(n):
	for j in range(n):
		if arr[i][j] == 1:
			dq.append((i,j))
			cnt +=1
			while dq:
				x,y = dq.pop()
				for k in range(len(dx)):
					nx = x+dx[k]
					ny = y+dy[k]
					if 0<=nx<n and 0<=ny<n:
						if arr[nx][ny] == 1:
							dq.append((nx,ny))
							arr[nx][ny] = 0
							
							
print(cnt)

1. DFS를 이용하여 1을 발견하면 끊어질때까지 탐색하고 끊어지면 cnt를 더하는 방법