[Python] 백준/BOJ 21736번: 헌내기는 친구가 필요해 (Silver 2)

💻 Problem

문제 보러 가기

 

도연이가 다니는 대학의 캠퍼스는 N×M 크기이며 캠퍼스에서 이동하는 방법은 벽이 아닌 상하좌우로 이동하는 것이다. 도연이가 이동할 수 있는 곳은 상하좌우이다. 단, 캠퍼스의 밖으로 이동할 수는 없다.

불쌍한 도연이를 위하여 캠퍼스에서 도연이가 만날 수 있는 사람의 수를 출력하는 프로그램을 작성해 보자.

O는 빈 공간, X는 벽, I는 도연이, P는 사람이다.

 

💡 Approach

먼저 도연이의 위치를 찾고 시작점으로 잡아 bfs를 돌린다.

4방향을 탐색할 때, 범위를 벗어나지 않고 벽이 아니면 이동할 수 있다.

이때, 탐색하려는 칸이 사람이면 cnt에 1을 더한다.

출력할 때는 삼항연산자를 써도 되지만, or를 쓰면 cnt가 0일 때 'TT'를 출력했다.

 

✏️ Solution

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

def bfs(x, y):
    dx = (-1, 1, 0, 0)
    dy = (0, 0, -1, 1)
    
    queue = deque([(x, y)])
    visited[x][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] and campus[nx][ny] != 'X':
                # 만약 다음 칸이 사람이면 만난 사람 수가 증가한다   
                if campus[nx][ny] == 'P':
                    cnt += 1
                # 이어서 탐색한다
                visited[nx][ny] = True
                queue.append((nx, ny))
    
    print(cnt or 'TT')

n, m = map(int, input().split())
campus = [input() for _ in range(n)]
visited = [[False] * m for _ in range(n)]

for i in range(n):
    for j in range(m):
        if campus[i][j]  == 'I':
            bfs(i, j)
            exit(0)

bfs를 탐색하는 시간복잡도는 O(V + E)이다.

여기서 간선의 개수는 4방향을 탐색하니 4V이고 더하면 총 5V가 된다.

정점의 개수는 n * m이므로 5V는 5 * n * m이다.

n, m은 총 600이므로 대입하면 18 * 10 ^ 5이다.