[백준] 21736번: 헌내기는 친구가 필요해 - Python

 링크: https://www.acmicpc.net/problem/21736

21736번: 헌내기는 친구가 필요해

아이디어

• I의 좌표를 찾고 그 지점부터 BFS진행
• P를 만나면 cnt +1
• X가 아닌 부분을 만나면 X로 바꿔주고(방문처리) 큐에 좌표를 넣어준다.
• BFS탐색이 끝난 후 cnt값을 return
• return된 값이 0이면 TT 아니면 값 그대로 출력

구현

import sys
input = sys.stdin.readline

from collections import deque


dy = [0, -1, 0, 1]
dx = [-1, 0, 1, 0]

def bfs():
    cnt = 0
    q = deque()
    q.append((y, x))

    while q:
        py, px = q.popleft()
        for i in range(4):
            ny = py + dy[i]
            nx = px + dx[i]
            if 0<= ny <n and 0<=nx<m:
                if li[ny][nx] == 'P':
                    cnt += 1
                if li[ny][nx] != 'X':
                    li[ny][nx] = 'X'
                    q.append((ny,nx))
    return cnt

n, m = map(int, input().split())
li = [list(input().strip()) for _ in range(n)]

for i in range(n):
    for j in range(m):
        if li[i][j] == 'I':
            x, y = j, i

result = bfs()

if result == 0:
    print("TT")
else:
    print(result)

마무리

• 시험기간이 다가와 시간이 오래걸리는 부담스런 문제는 피하려 한다..
• 단순 그래프 탐색문제