[CT] 백준 2667 단지번호 붙이기 / 백준 2606 바이러스(DFS & BFS)

1. 백준 2667 단지번호 붙이기

.
.

📎단지번호 붙이기

🤷‍♂️ 풀이방법 - 큐(BFS)

import sys
from collections import deque

# 상하좌우 탐색을 위한 전역변수 설정
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
N = 0
house_map = []  # 원본 배열
visited = []    # 방문 배열


def house(x, y):
    global house_map, visited
    queue = deque()
    queue.append((x, y))
    visited[x][y] = True
    count = 1  # 현재 단지의 집 수

    while queue:
        now_x, now_y = queue.popleft()
        for i in range(4):
            nx = now_x + dx[i]
            ny = now_y + dy[i]
            if 0 <= nx < N and 0 <= ny < N and house_map[nx][ny] == 1 and not visited[nx][ny]:
                visited[nx][ny] = True
                queue.append((nx, ny))
                count += 1
    return count


if __name__ == "__main__":
    N = int(sys.stdin.readline().strip())
    house_map = [list(map(int, sys.stdin.readline().strip())) for _ in range(N)]
    visited = [[False] * N for _ in range(N)]
    counts = []

    for i in range(N):
        for j in range(N):
            if house_map[i][j] == 1 and not visited[i][j]:
                counts.append(house(i, j))

    print(len(counts))
    counts.sort()
    for count in counts:
        print(count)

• 자바로 한 번 풀었던 문제였어서 파이썬으로 옮기는데 그렇게 어렵지는 않았지만 두 언어에서 어떤식으로 돌아가는지 확인할 수 있었다.
  .
  .

---

2. 백준 2606 바이러스

📎바이러스

🤷‍ 풀이방법 1 - 재귀(DFS)

✅ 1번 - sys 사용 안함

• 메모리 : 31120KB / 시간: 48ms

def computer(start):
    # 전역 변수 설정
    global virus, visited, graph
    # queue = deque([start])
    # 처음 visited[1] 방문
    visited[start] = True

    for x in graph[start]:
        if not visited[x]:
            virus += 1
            visited[x] = True
            computer(x)


if __name__ == "__main__":
    n = int(input())
    number = int(input())
    # 원본 배열
    graph = [[] for _ in range(n + 1)]      # 1부터임
    # 방문 여부 배열
    visited = [False] * (n + 1)             # 1부터임
    # 바이러스 개수 변수
    virus = 0

    for i in range(number):
        u, v = map(int, input().split())
        # 단방향 그래프 설정 -> 자바 코드에서 참고
        graph[u].append(v)
        graph[v].append(u)

    computer(1)
    print(virus)

✅ 2번 - sys 사용

• 메모리 : 31120KB / 시간 : 40ms

# from collections import deque 
import sys

def computer(start):
    global virus, visited, graph
    visited[start] = True

    for x in graph[start]:
        if not visited[x]:
            virus += 1
            visited[x] = True
            computer(x)

if __name__ == "__main__":
    n = int(sys.stdin.readline().strip())
    number = int(sys.stdin.readline().strip())
    graph = [[] for _ in range(n + 1)]
    visited = [False] * (n + 1)
    virus = 0

    for i in range(number):
        u, v = map(int, sys.stdin.readline().strip().split())
        graph[u].append(v)
        graph[v].append(u)

    computer(1)
    print(virus)

• 처음에 걸리는 시간 단축을 위해 import sys 를 하여 입력을 받게 했다. 그런데 오히려 시간이 80ms 로 sys 를 사용하지 않을 때 보다 시간이 더 걸렸는데

from collections import deque

위 import 부분때문이었다. 처음에 큐를 사용해서 문제를 풀었어서 그냥 import 문을 안지우고 사용하지 않으면 상관 없을거라고 생각했는데 무려 2배나 시간을 잡아먹을 정도로 문제가 있었던 것을 알았다.

🤷‍ 풀이방법 2 - 큐(BFS)

• 메모리 : 34052KB / 시간 : 64ms

from collections import deque

def computer(start):
    global count, visited, graph
    queue = deque([start])
    visited[start] = True

    while queue:
        current = queue.popleft()
        for neighbor in graph[current]:
            if not visited[neighbor]:
                visited[neighbor] = True
                count += 1
                queue.append(neighbor)

if __name__ == "__main__":
    n = int(input())
    number = int(input())
    graph = [[] for _ in range(n+1)]
    visited = [False] * (n+1)
    count = 0

    for _ in range(number):
        u, v = map(int, input().split())
        graph[u].append(v)
        graph[v].append(u)

    computer(1)
    print(count)