[Python] 백준, 2667(BFS/DFS)

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

2667번: 단지번호붙이기

분류는 BFS지만 DFS로도 구현할 수 있는 문항이다. 이전 문제와 마찬가지로 전형적인 BFS/DFS 문제라는데 아직 어려운 것 같다.. 코드 또한 상당히 비슷하긴 하다.

 

# PYTHON CODE(1) - BFS

import sys


def bfs(tree, a, b):
    cnt = 1  #  아래 for문이 실행할 때 tree값이 1일때부터 확인하므로 0이 아니라 1로 설정.
    queue = deque()
    queue.append([a, b])
    tree[a][b] = 0  #  cnt가 1인 이유와 동일.

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

    while queue:
        x, y = queue[0]
        del queue[0]  #  deque모듈의 popleft()가 은근 시간이 걸려서 이것도 괜찮은 것 같다.

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or nx >= n or ny < 0 or ny >= n:
                continue

            if tree[nx][ny] == 1:
                cnt += 1
                tree[nx][ny] = 0  #  이 한줄이 아래 이중 for문의 효율성을 엄청 높여준다
                queue.append([nx, ny])

    return cnt


n = int(sys.stdin.readline())
tree = [list(map(int, sys.stdin.readline().rstrip())) for _ in range(n)]
answer = []

for i in range(n):
    for j in range(n):
        if tree[i][j] == 1:
            answer.append(bfs(tree, i, j))

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

 

 

# PYTHON CODE (2) - DFS

import sys

n = int(input())
tree = [list(map(int, sys.stdin.readline().rstrip())) for _ in range(n)]
count = 0
answer = []

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


def dfs(tree, a, b):
    if a < 0 or a >= n or b < 0 or b >= n:  #  아래 for문에서 다른 조건 없이 dfs의 bool값을 물어보므로 맨 위에 이 조건문이 필수다.
        return False

    global count  #  count값 갱신의 용이함을 위한 전역변수 설정.

    if tree[a][b] == 1:
        tree[a][b] = 0
        count += 1
        for i in range(4):
            na = a + dx[i]
            nb = b + dy[i]
            dfs(tree, na, nb)
        return True  #  이 부분이 살짝 애매하게 와닿는데, 재귀로 dfs가 반복되면 언젠가 false가 return될텐데 선후 관계에서 return True가 앞서나보다.
    return False


for i in range(n):
    for j in range(n):
        if dfs(tree, i, j):
            answer.append(count)
            count = 0

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

 

 

실버1인데 이 정도의 사고력을 요구한다면, 알고리즘 자체가 어렵다고 봐도 무방한 것 같다.