[백준/파이썬] 21736번: 헌내기는 친구가 필요해

문제

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

풀이

• $N \times M$ 크기
• 상하좌우 이동
• O: 빈 공간, X: 벽, I: 도연이, P: 사람
• 만날 수 있는 사람의 수 출력
  • 못만날 경우 TT 출력

BFS를 활용한 문제
DFS로 풀 경우 깊이가 깊어질 수 있어 스택오버플로우 발생이 가능

입력값을 2차원 리스트로 저장

graph = []
for i in range(n):
	r = list(input().strip())
    graph.append(r)

저장하려는 리스트 r을 이용해 도연이의 위치 탐색

	for j in range(m):
    	if r[j] == "I":
        	start_x,start_y = i, j

탐색하기 위해 도연이의 이동방향(상하좌우) 설정

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

BFS를 사용하여 탐색 진행

def bfs(start_x, start_y):
	queue = deque([(start_x, start_y)]) # 큐에 시작 지점 추가
    visited[start_x][start_y] = True # 방문 처리
    cnt = 0 # 만난 사람의 수
    
    while queue:
        x,y = queue.popleft() # 현재 위치
        for i in range(4): # 4방향 탐색
            nx,ny = x+dx[i], y+dy[i]

범위 내에서 탐색 시작

            if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]: # 0 이상 (n,m) 미만, 방문하지 않은 곳일 때
                if graph[nx][ny] != "X": # 벽을 만났을 경우 탐색 진행 x
                    queue.append((nx,ny)) # 이동한 위치 큐에 추가
                    visited[nx][ny] = True # 방문 처리
                    if graph[nx][ny] == "P": # 이동한 좌표가 빈공간이 아닌 사람일 경우
                        cnt += 1 # 카운트 증가
    return cnt

최종적으로 만난 사람 수를 출력해주면 됩니다.

	res = bfs(start_x,start_y)
    print(res if res > 0 else "TT") # 아무도 못 만났다면 "TT" 출력

코드

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

def bfs(start_x, start_y):
    queue = deque([(start_x, start_y)])
    visited[start_x][start_y] = True
    cnt = 0

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

if __name__ == "__main__":
    n,m = map(int,input().split())
    
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    graph = []
    start_x,start_y = 0,0
    for i in range(n):
        r = list(input().strip())
        graph.append(r)
        for j in range(m):
            if r[j] == "I":
                start_x,start_y = i,j

    visited = [[False] * m for _ in range(n)]
    res = bfs(start_x,start_y)
    print(res if res > 0 else "TT")