[Baekjoon]백준 21736 헌내기는 친구가 필요해(실버 2) - Python

문제설명

문제를 살펴보면 어떠한 하나의 위치에서 상하좌우로 움직여 벽을 피해 사람을 찾는 문제이다

즉, 해당 문제는 최근들어 자주 사용한 bfs를 사용하여 해결할 수 있다

 

row, col 변수에 캠퍼스의 크기를 저장하고 campus 리스트에 캠퍼스의 정보를 저장한다

이후 for문을 돌면서 도연이가 위치한 곳을 찾고 해당 위치를 기록해준다

이렇게 찾은 도연이의 위치를 bfs함수를 통해 이동가능한 공간에 사람이 존재하는지,

존재한다면 cnt 변수에 1씩 더해준다

이번에 해결할 때에는 visited 리스트를 정의하여 도연이가 이미 만난 사람인지 판단하도록 하였다

import sys
from collections import deque

input = sys.stdin.readline

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

def bfs(sx, sy):
    queue = deque()
    queue.append((sx, sy))
    visited[sx][sy] = True
    cnt = 0
    
    while queue:
        x, y = queue.popleft()
        if campus[x][y] == 'P':
            cnt += 1
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < row and 0 <= ny < col and not visited[nx][ny]:
                if campus[nx][ny] != 'X':
                    visited[nx][ny] = True
                    queue.append((nx, ny))
    return cnt

row, col = map(int, input().split())
campus = [list(input().strip()) for _ in range(row)]
visited = [[False] * col for _ in range(row)]

start_x = start_y = -1
for i in range(row):
    for j in range(col):
        if campus[i][j] == 'I':
            start_x, start_y = i, j

result = bfs(start_x, start_y)
if result == 0:
    print("TT")
else:
    print(result)