문제
https://www.acmicpc.net/problem/21736
풀이
너비우선탐색(BFS)을 통해 만날 수 있는 사람이 몇 명인지 찾아낸다.
현재 위치인 'I'의 좌표를 찾고 이를 시작점으로 하여 q에 삽입한다.
q의 첫 번째 값을 pop 하고, 이 값의 상하좌우를 확인하여
표의 범위를 벗어나지 않고 벽('X')이 아니라면 (+방문하지 않았다면),
해당 위치를 방문했다고 값을 변경하고, q에 삽입한다.
이때 P라면 ans를 증가시킨다.
위 과정을 더 이상 방문할 곳이 없을 때까지 반복한다.
코드
import sys
input = sys.stdin.readline
from collections import deque
n, m = map(int, input().split())
board = [list(input().rstrip()) for _ in range(n)]
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
for i in range(n):
for j in range(m):
if board[i][j] == 'I':
x, y = i, j
board[i][j] == 'X'
q = deque([])
q.append((x, y))
ans = 0
while q:
x, y = q.popleft()
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if 0 <= nx < n and 0 <= ny < m and board[nx][ny] != 'X':
if board[nx][ny] == 'P':
ans += 1
board[nx][ny] = 'X'
q.append((nx, ny))
print('TT' if ans == 0 else ans)
'Koala - 12기 > 코딩테스트 준비 스터디' 카테고리의 다른 글
[백준/Python3] 29687번 : Игра (2) | 2023.11.20 |
---|---|
[백준/C++] 5464번: 주차장 (0) | 2023.11.20 |
[백준/C++] 5464번 주차장 (0) | 2023.11.18 |
[백준python] 5464번: 주차장 (0) | 2023.11.15 |
[백준/Python] 1446번 : 지름길 (1) | 2023.11.13 |