백준 파이썬 21736번 헌내기는 친구가 필요해 (Today I Learn 2025.02.05)

백준 파이썬 공부 2025.02.05
21736번 헌내기는 친구가 필요해 (실버 2)

1. 문제
2020년에 입학한 헌내기 도연이가 있다. 
도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 
드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 싶다. 

도연이가 다니는 대학의 캠퍼스는 N * M 크기이며 캠퍼스에서 이동하는 방법은 벽이 아닌 상하좌우로 이동하는 것이다. 
예를 들어, 도연이가 (x, y)에 있다면 이동할 수 있는 곳은 (x+1, y), (x, y+1), (x-1, y), (x, y-1)이다. 
단, 캠퍼스의 밖으로 이동할 수는 없다.

불쌍한 도연이를 위하여 캠퍼스에서 도연이가 만날 수 있는 사람의 수를 출력하는 프로그램을 작성해보자.

2. 입력
첫째 줄에는 캠퍼스의 크기를 나타내는 두 정수 
N (1 <= N <= 600), M (1 <= M <= 600)이 주어진다.

둘째 줄부터 N개의 줄에는 캠퍼스의 정보들이 주어진다. 
O는 빈 공간, X는 벽, I는 도연이, P는 사람이다. I가 한 번만 주어짐이 보장된다.

3. 출력
첫째 줄에 도연이가 만날 수 있는 사람의 수를 출력한다. 
단, 아무도 만나지 못한 경우 TT를 출력한다.

4. 문제 풀이
그래프 문제이다.
당연히 DFS, BFS를 사용하여 풀어야한다.

일단 BFS를 사용해서 풀어보자
>>>코드 1. BFS 사용

import sys
from collections import deque

def BFS(y, x):
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    
    cnt = 0
    queue.append((y, x))
    visited[y][x] = 1
    
    while queue:
        y, x = queue.popleft()
        if graph[y][x] == 'P':
            cnt += 1
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0 <= nx < m and 0 <= ny < n:
                if visited[ny][nx] == 0 and graph[ny][nx] != 'X':
                    queue.append((ny, nx))
                    visited[ny][nx] = 1
    return cnt

n, m = map(int, sys.stdin.readline().split())
graph = []
for _ in range(n):
    graph.append(sys.stdin.readline())

flag = 0
queue = deque()
visited = [[0] * m for _ in range(n)]
for i in range(n):
    for j in range(m):
        if graph[i][j] == 'I':
            cnt = BFS(i, j)
            flag = 1
            break
    if flag:
        break

if cnt:
    print(cnt)
else:
    print("TT")

다음으로는 DFS를 사용해서 풀어보자
DFS를 사용할 경우 recursion error가 발생하는데,
이는 파이썬에서 함수가 너무 많은 재귀호출을 할 때 발생하므로,
sys.setrecursionlimit(10**6) 로 재귀 깊이를 늘려 줘야한다.
그러나 이 방식보다는 BFS를 사용하는 것을 권장한다.

>>>코드2. DFS 사용

import sys
sys.setrecursionlimit(10**6)

def DFS(y, x, cnt):
    if graph[y][x] == 'P':
        cnt += 1
    
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        
        if 0 <= nx < m and 0 <= ny < n:
            if visited[ny][nx] == 0 and graph[ny][nx] != 'X':
                visited[ny][nx] = 1
                cnt = DFS(ny, nx, cnt)
    return cnt

n, m = map(int, sys.stdin.readline().split())
graph = []
for _ in range(n):
    graph.append(sys.stdin.readline())

flag = 0
visited = [[0] * m for _ in range(n)]
for i in range(n):
    for j in range(m):
        if graph[i][j] == 'I':
            visited[i][j] = 1
            cnt = DFS(i, j, 0)
            flag = 1
            break
    if flag:
        break

if cnt:
    print(cnt)
else:
    print("TT")

5. 문제 링크
https://www.acmicpc.net/problem/21736