🗂️ 문제
링크: https://www.acmicpc.net/problem/2667
💡 접근법
DFS를 사용하여 연결된 집의 개수를 구한다.
이때 dx와 dy 리스트를 통해 현재 위치에서 상하좌우로 이동할 수 있게 하고, 이동한 좌표가 1) 지도 밖을 벗어나지 않는지, 2) 집이 존재하는지, 3) 방문한 적이 없는지를 확인한다.
모든 조건을 만족할 경우 재귀로 DFS를 수행하고, 수행한 횟수를 cnt로 계산한다.
해당 값이 단지에 속하는 집의 개수가 된다.
😎 내 코드
import sys
N = int(sys.stdin.readline())
house_num = []
visited = [[False] * N for _ in range(N)]
maps = []
for _ in range(N):
maps.append(list(map(int, sys.stdin.readline().rstrip())))
# 상하좌우
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
def DFS(x, y):
global cnt
visited[x][y] = True
cnt += 1
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < N and 0 <= ny < N: # 지도 밖을 벗어나지 않는지 확인
if maps[nx][ny] and not visited[nx][ny]: # 집이 있고 방문한 적이 없는 경우
DFS(nx, ny)
for x in range(N):
for y in range(N):
if maps[x][y] and not visited[x][y]:
cnt = 0
DFS(x, y)
if cnt != 0:
house_num.append(cnt)
print(len(house_num))
for h in sorted(house_num):
print(h)
✅ 정답 확인
'Algorithm > Baekjoon' 카테고리의 다른 글
[BFS] 백준 #7562 나이트의 이동 - Python (0) | 2024.05.26 |
---|---|
[큐] 백준 #1966 프린터 큐 - Python (0) | 2024.05.26 |
[BFS] 백준 #1325 효율적인 해킹 - Python (0) | 2024.05.14 |
[그래프] 백준 #1753 최단경로 - Python (0) | 2024.05.11 |
[BFS] 백준 #18352 특정 거리의 도시 찾기 - Python (0) | 2024.05.11 |