(백준) 2667번: 단지번호붙이기 파이썬 풀이(BFS&DFS)

<포스팅 요약>

1. 문제풀러가기

2. 문제 해결 코드

3. 로직 분석

---

1. 문제풀러가기

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

2667번: 단지번호붙이기

 

문제 해석:

- 1로 이어진 부분을 체크하고, 이어진 부분의 개수 출력하기

---

2. 문제 해결 코드

코드 (성공) DFS풀이

import sys
input = sys.stdin.readline

n = int(input())
v = [[False for _ in range(n)] for _ in range(n)] #방문체크 리스트
arr = [str(input()) for _ in range(n)] #단지 리스트
dn = [(0, -1), (0, 1), (-1, 0), (1, 0)] #네 방향
cnt = 0 
res = []


def dfs(i, j):
    global cnt
    v[i][j] = True #탐색한 위치 방문 체크
    cnt += 1
    for x, y in dn: #현재위치에서 4방향으로 체크
        dx = i+x
        dy = j+y
        if 0 <= dx < n and 0 <= dy < n: #리스트 범위안에 있는지 체크
            if v[dx][dy] == False and arr[dx][dy] == "1": 
            #방문을 안했으며 단지리스트에서 0이아닌 1일경우
                dfs(dx, dy)


for i in range(n):
    for j in range(n):
        if v[i][j] == False and arr[i][j] == "1": #방문하지 않은곳과 "1"인 곳만 탐색
            dfs(i, j)
            res.append(cnt)
            cnt = 0
            
res.sort() #오름차순 정렬
print(len(res)) #단지 개수 출력
for i in res:
    print(i)

 

코드 (성공) BFS풀이

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

n = int(input())
arr = [str(input()) for _ in range(n)]
v = [[False for _ in range(n)] for _ in range(n)]
dn = [(-1, 0), (1, 0), (0, 1), (0, -1)]


def bfs(i, j):
    cnt = 0
    queue = deque([(i, j)])
    v[i][j] = True
    while queue:
        x, y = queue.popleft()
        cnt += 1
        for q, w in dn:
            dx = x+q
            dy = y+w
            if 0 <= dx < n and 0 <= dy < n:
                if v[dx][dy] == False and arr[dx][dy] == "1":
                    queue.append((dx, dy))
                    v[dx][dy] = True

    return cnt


res = []
for i in range(n):
    for j in range(n):
        if v[i][j] == False and arr[i][j] == "1":
            res.append(bfs(i, j))

print(len(res))
res.sort()
for i in res:
    print(i)

 

BFS 혹은 DFS 두 알고리즘중 하나로 풀 수 있는 문제이다.

풀이에서 BFS와 DFS두 로직이 비슷하다.

 

---

3. 로직분석

1) 현재 위치 i,j에서 네 방향을 for문으로 체크한다.

2) 방문하지 않았고 arr[dx][dy]=="1"인 곳만 탐색하여 개수를 체크해준다.