📚 2667 - 단지번호붙이기

단지번호붙이기

풀이

• 그래프(백트래킹) 문제이다.
• 일종의 트리 탐색 알고리즘이다.

다만, dfs/bfs 어떤게 더 빠를까?

백트래킹 - 나무위키 에 따르면

🔔 DFS와 BFS 언제 사용될까?
(1) DFS를 써야할 때

• 모든 경우의 수를 고려해야 하는 문제라면, DFS를 사용한다.
• BFS로도 구현이 물론 가능하지만, BFS로 구현했다간 큐의 크기가 증가한다. 심지어 속도도 똑같다.
• 따라서 경우의 수 구하기는 일반적으로 DFS가 편리하다. 대다수의 문제들은 DFS를 써도 일단 답은 나온다.

(2) BFS를 써야할 때

• 트리의 깊이가 무한대가 될 때이다.
  • 미로찾기에서 루프(회로)가 발생하는 경우, DFS는 이 가지를 탈출할 수 없게 된다. (DFS 사용시, 스택 오버플로우 발생 가능함)
• 트리 깊이 무한대이거나, 미로찾기에서 회로가 발생하는 경우에는 BFS가 편하다.
• 최단거리 구하기 문제에서는 BFS를 사용한다.

이 문제는? 모든 경우의 수를 고려하여 총 단지수를 출력해야 한다. dfs를 사용하는게 좋다.

소스

dfs

import sys

sys.setrecursionlimit(111111)

x_coordinate = [-1 , 0 , 1, 0]
y_coordinate = [0, 1, 0, -1]



def dfs(x, y):
    global result
    result += 1
    visited[x][y] = True

    for i in range(4):
        next_x = x_coordinate[i] + x
        next_y = y_coordinate[i] + y

        if 1<= next_x <= n and 1 <= next_y <=n:
            if visited[next_x][next_y] or graph[next_x][next_y] == 0:
                continue

            dfs(next_x, next_y)


n = int(sys.stdin.readline())

graph = [0]
visited = [[False] * (n+1) for _ in range(n+1)]

total_list = []

for idx in range(n):
    in_graph = list(sys.stdin.readline().strip())
    graph.append([0] + list(map(int, in_graph)))

for i in range(1,n+1):
    for j in range(1, n+1):
        if not visited[i][j] and graph[i][j] == 1:
            result = 0
            dfs(i, j)
            total_list.append(result)

total_list.sort()
print(len(total_list))
print('\n'.join(map(str, total_list)))

채점 결과

bfs

import sys
from collections import deque


x_coordinate = [-1 , 0 , 1, 0]
y_coordinate = [0, 1, 0, -1]

def bfs(x, y):
    queue = deque()
    # print("현재 좌표 : ", x, y)
    queue.append((x, y))
    visited[x][y] = True
    result = 1
    while queue:
        x_out, y_out = queue.popleft()

        for i in range(4):
            next_x = x_out + x_coordinate[i]
            next_y = y_out + y_coordinate[i]

            if next_x < 1 or next_x > n or next_y < 1 or next_y > n:
                continue
            if visited[next_x][next_y]:
                continue
            if graph[next_x][next_y] == 0:
                continue
            visited[next_x][next_y] = True
            result += 1
            queue.append((next_x, next_y))
    return result

n = int(sys.stdin.readline())

graph = [0]
visited = [[False] * (n+1) for _ in range(n+1)]

total_list = []

for idx in range(n):
    in_graph = list(sys.stdin.readline().strip())
    graph.append([0] + list(map(int, in_graph)))

# print(graph)

for i in range(1,n+1):
    for j in range(1, n+1):
        if not visited[i][j] and graph[i][j] == 1:
            result = bfs(i, j)
            total_list.append(result)

total_list.sort()

print(len(total_list))
print('\n'.join(map(str, total_list)))

채점 결과