251211 코테연습 기록

유기농 배추 (백준)

• 문제 유형 : DFS 또는 BFS
• BFS로 일단 해봤으나 시간초과
• 항상 DFS/BFS 맵 탐색 유형은 더 효율적인 풀이가 없을지 생각해야 한다..
  (하지만 사실 이 문제는 효율의 문제가 아니었음)

제출 코드 (시간초과)

import sys
input = sys.stdin.readline

from collections import deque

direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]

t = int(input())
for _ in range(t):
    m, n, k = map(int, input().split())  # m -> c, n -> r
    cabbage = [[0] * m for _ in range(n)]

    for _ in range(k):
        a, b = map(int, input().split())
        cabbage[b][a] = 1

    count = 0
    queue = deque()
    for i in range(n):
        for j in range(m):
            if cabbage[i][j] == 1:
                queue.append((i, j))
                while queue:
                    r, c = queue.popleft()
                    cabbage[r][c] = 0
                    for dr, dc in direction:
                        if 0 <= r + dr < n and 0 <= c + dc < m:
                            if cabbage[r + dr][c + dc] == 1:
                                queue.append((r + dr, c + dc))
                count += 1
    print(count)

모든 좌표를 일단 체크하는 부분이 문제일 것 같아서, 미리 배추 좌표를 리스트에 모아뒀다가 그 좌표들만 순회하면 어떨까 하고 수정했지만, 여전히 시간초과

결국 원인은.. 큐에 일단 넣고 뺄 때 방문처리(0으로 만들기)한 게 문제였다
고질적인 실수 유형 하나 찾았다

정답 코드 (BFS, 해당 부분만 수정)

    for i, j in cabbage:
        # for j in range(m):
        if cabbage_map[i][j] == 1:
            queue.append((i, j))
            cabbage_map[i][j] = 0
            while queue:
                r, c = queue.popleft()
                #cabbage_map[r][c] = 0
                for dr, dc in direction:
                    if 0 <= r + dr < n and 0 <= c + dc < m:
                        if cabbage_map[r + dr][c + dc] == 1:
                            queue.append((r + dr, c + dc))
                            cabbage_map[r+dr][c+dc] = 0
            count += 1
    print(count)

이 문제는 DFS로도 다음과 같이 풀 수 있다. 다만 재귀 제한을 해제해야 한다.

정답 코드 (DFS)

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10**6)

direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]

t = int(input())
for _ in range(t):
    m, n, k = map(int, input().split())  # m -> c, n -> r
    cabbage_map = [[0] * m for _ in range(n)]
    cabbage = []

    for _ in range(k):
        a, b = map(int, input().split())
        cabbage_map[b][a] = 1
        cabbage.append((b, a))

    count = 0

    def dfs(r, c):
        if 0 <= r < n and 0 <= c < m:
            if cabbage_map[r][c] == 0:
                return

            cabbage_map[r][c] = 0

            for dr, dc in direction:
                dfs(r + dr, c + dc)
   
        else:
            return

    for i, j in cabbage:
        if cabbage_map[i][j] == 1:
            dfs(i, j)
            count += 1

    print(count)