[Python]Baekjoon 21736번: 헌내기는 친구가 필요해(BFS)

1. 문제

 

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

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

 

캠퍼스(그래프)를 이동하면서 주인공이 만날 수 있는 사람의 수를 구하는 문제이다.

 

O는 빈공간, P는 사람, X는 벽, I는 주인공의 위치이다.

 

2. 풀이

첫번째로 주의해야 하는 부분은 그래프의 입력을 공백 단위로 받지 않고 문자열로 받고 있다는 점이다.

 

처음에는 조금 당황했는데 그냥 똑같이 list에 넣으면 똑똑한 파이썬이 알아서 처리해주었다.

 

두번째로 주의해야 하는 부분은 주인공의 위치가 정해져 있지 않다는 점이다.

 

그렇기 때문에 주인공의 위치를 2중 반복문을 통해서 찾고 이를 큐에 저장하였다.

 

그리고 이 큐를 bfs 함수에 전달한다.

 

그래프 탐색은 일반적인 BFS와 똑같이 진행해주면 되고,

 

만약에 다음칸이 'P'인경우 answer에 1을 더해주는 조건문만 추가해주면 된다.

3. 코드

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

N, M = map(int, input().split())
graph = [input() for _ in range(N)]
visited = [[-1]*M for _ in range(N)]
queue = deque()

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

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

for i in range (N):
    for j in range(M):
        if graph[i][j] == 'I':
            queue.append([i,j])

answer = bfs(queue)

if answer:
    print(answer)
else:
    print('TT')

 

뜬금없이 헷갈렸던 부분인데 아래의 코드를 이용해서 초기화하면

 

visited = [[-1]*M for _ in range(N)]

 

[[-1, -1, -1, -1],
 [-1, -1, -1, -1],
 [-1, -1, -1, -1]]

 

위와 같은 리스트가 생성된다.