문제 바로가기

t : 테스트 케이스 개수
m : 가로(열), n: 세로(행), k: 배추개수
(x,y) 배추위치 (x:가로, y:세로)

🔍 나의 코드 (BFS)

# BFS
from collections import deque

def bfs(x, y):
    q = deque()
    q.append((x, y))
    maps[y][x] = 2 #방문처리

    while q:
        x, y = q.popleft()

        for i in range(4):
            tx = x + dx[i]
            ty = y + dy[i]
			
            # maps의 범위 안에 있고 방문하지 않은 배추가 있으면
            if 0<=tx<=m-1 and 0<=ty<=n-1 and maps[ty][tx]==1:
                q.append((tx, ty))
                maps[ty][tx] = 2 #방문처리




# t: 테스트케이스개수
t = int(input())

#상하좌우
dx = [0, 0, -1, 1] #가로/열
dy = [-1, 1, 0, 0] #세로/행

for _ in range(t):
        
    # m:가로/열, n:세로/행, k:배추개수
    m, n, k = map(int, input().split())

    cnt = 0
    location = []
    maps = [[0] * m for _ in range(n)] #2차원리스트 초기화



    # 배추의 위치 입력받기
    for _ in range(k):
        x, y = map(int, input().split())
        location.append((x, y))
        maps[y][x] = 1


    # 배추위치마다 필요한 흰지렁이 개수 조사
    for x, y in location:
        if maps[y][x]==1:
            dfs(x, y)
            cnt += 1

    print(cnt)

🔍 나의 코드 (DFS)

#DFS
import sys
sys.setrecursionlimit(10000)

def dfs(x, y):
    maps[y][x] = 2 #방문처리

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

            # maps의 범위 안에 있고 방문하지 않은 배추가 있으면
            if 0<=tx<=m-1 and 0<=ty<=n-1 and maps[ty][tx]==1:
                bfs(tx, ty) #dfs로 풀려면 dfs(tx, ty)해주면 됨.
                maps[ty][tx] = 2 #방문처리

RecursionError

import sys
sys.setrecursionlimit(10000)

BOJ의 채점 서버에서 파이썬의 최대 재귀 깊이는 1,000으로 되어 있다. 따라서 이보다 큰 재귀가 발생하는 경우 추가로 최대 재귀 깊이를 재설정해주지 않으면 Error가 난다.

📌 코드 풀이

DFS와 BFS 모두 사용가능한 문제이다.

• 테스트케이스 개수 t 입력받고, t만큼 반복
• m,n,k입력받음
• k만큼 배추의 위치 입력받음. 이때 함께 배추의 위치만 따로 리스트location에 저장해둠.
• 배추의 위치를 저장한 리스트 location을 for문으로 돌면서 방문하지않은 배추가 있을경우(maps[][]==1), bfs()를 수행하고 cnt를 +1해준다.
  - cnt : 필요한 배추흰지렁이 마리 수
  - bfs() : 현재위치에서 상하좌우 인접한 배추를 확인하고 방문처리를 함.

방문한 위치를 체크하기위해 방문한 곳은 maps의 값을 2로 바꾸어 주었다.

• 방문처리는 언제 해주어야 하는가?
  방문처리를 bfs()의 맨 마지막줄(if문 안)에서 해주지 않고 q.popleft() 다음에 해주었더니 시간초과가 떴다.
  방문처리를 함은 중복된 탐색을 하지 않기 위함이다. 하지만 (전자의 방법)큐에 추가하면서 방문처리를 바로 해주지 않으면 방문처리를 하지 않았을 때와 같은 상황이 되어 중복으로 탐색되는 경우가 생긴다.

🔍 다른 코드

• 굳이 location변수를 만들 필요없이 이중for문으로 maps전체의 요소를 돌며 maps[][]==1인 것을 찾아도 된다.

for x in range(m):
        for y in range(n):
            if maps[y][x] == 1:
                bfs(x, y)
                cnt += 1

💫 Comment

책의 '음료수 얼려 먹기 문제'와 동일한 유형이다.
bfs, dfs를 어떤 상황에 써야 유리한지 아직은 헷갈린다.
오류1 : 방문처리를 언제 해줘야하는지 헷갈려서 처음엔 시간초과가 떴다.
오류2 : dfs의 RecursionError
이 문제에서는 행이 x,n고 열이 y,m임. 헷갈리지 않게 조심!