[백준] 21736번 헌내기는 친구가 필요해

💡문제접근

• 너비 우선 탐색(BFS) 알고리즘을 이용해서 코드를 작성했다. 방문 여부를 나타내는 배열 visited와 캠퍼스를 나타내는 배열 campus 두 개의 배열을 이용했고 조건별로 조건문을 작성하여 도연이가 만날 수 있는 사람의 수를 출력하도록 코드를 작성했다.

💡코드(메모리 : 39556KB, 시간 : 508ms)

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

N, M = map(int, input().strip().split())
campus = []
visited = [[False] * M for _ in range(N)]
for i in range(N):
    lst = list(input().strip())
    campus.append(lst)

cnt = 0
def BFS(a, b):
    global cnt
    queue = deque()
    queue.append((a, b))
    visited[a][b] = True
    while queue:
        x, y = queue.popleft()
        dx = [0, 1, 0, -1]
        dy = [-1, 0, 1, 0]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= N or ny < 0 or ny >= M:
                continue
            if 0 <= nx < N and 0 <= ny < M:
                if not visited[nx][ny]:
                    if campus[nx][ny] == "O":
                        queue.append((nx, ny))
                        visited[nx][ny] = True
                    elif campus[nx][ny] == "P":
                        queue.append((nx, ny))
                        visited[nx][ny] = True
                        cnt += 1
                    else:
                        continue
    if cnt == 0:
        return "TT"
    else:
        return cnt

for i in range(N):
    for j in range(M):
        if campus[i][j] == "I":
            print(BFS(i, j))

💡소요시간 : 17m