[백준] 21739 | 헌내기는 친구가 필요해 [파이썬/python

문제

link: https://www.acmicpc.net/problem/21736

캠퍼스 지도를 입력받아, 도연이가 캠퍼스에서 만날 수 있는 사람의 수를 출력하는 문제이다.

I는 출발점(현재 도연이가 위치하는 곳)이다.

P는 사람이다.

O는 빈 공간이다.

X는 벽으로, 막혀 있기 때문에 이동할 수 없다.

 

접근

도연이가 캠퍼스에서 만날 수 있는 사람의 수를 출력해야 하므로, I에서부터 출발해 I와 연결된 공간만 순회하면 된다. 따라서 I의 좌표를 찾아 따로 저장해두었다.

X를 제외한 공간을 순회하며 P의 개수를 세고, 답을 출력하도록 했다.

처음에는 재귀를 활용해 DFS로 구현했는데, 시간 초과가 발생해 BFS로 다시 구현했다.

(DFS로 구현한 코드)

 

import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline

def findI(campus):
    for i in range(N):
        for j in range(M):
            if campus[i][j] == 'I':
                return [i, j]

def wander(campus, x, y):
    global cnt
    if campus[x][y] == 'X':
        return
    if campus[x][y] == 'P':
        cnt[0] += 1
    campus[x][y] = 'X'
    
    for i in range(4):
        xx = x + dx[i]
        yy = y + dy[i]
        if 0 <= xx < N and 0 <= yy < M:
            wander(campus, xx, yy)  

N, M = map(int, input().split())
campus = [list(input().strip()) for _ in range(N)]
dx = (-1, 1, 0, 0)
dy = (0, 0, -1, 1)
cnt = [0]

I = findI(campus)

wander(campus, I[0], I[1])
print(cnt[0] if cnt[0] else 'TT')

 

코드

import sys
from collections import deque
input = sys.stdin.readline

def findI(campus):
    for i in range(N):
        for j in range(M):
            if campus[i][j] == 'I':
                return (i, j)

def wander(x, y):
    cnt = 0 
    v = [[0]*M for _ in range(N)]
    v[x][y] = 1
    q = deque()
    q.append((x, y))
    
    while q:
        x, y = q.popleft()
        if campus[x][y] == 'P':
            cnt += 1
            
        for i in range(4):
            xx = x + dx[i]
            yy = y + dy[i]
            if 0 <= xx < N and 0 <= yy < M and not v[xx][yy] and campus[xx][yy] != 'X':
                v[xx][yy] = 1
                q.append((xx, yy))
                
    return cnt

N, M = map(int, input().split())
campus = [input().strip() for _ in range(N)]
dx = (-1, 1, 0, 0)
dy = (0, 0, -1, 1)

I = findI(campus)

cnt = wander(I[0], I[1])
print(cnt if cnt else 'TT')