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

🔗 문제 링크

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

⏰ 소요된 시간

40분

✨ 수도 코드

1. 문제 이해

I: 도연이의 현재 위치
P: 사람의 위치
O: 빈 공간 (도연이가 움직일 수 있는 위치)
X: 벽 (도연이가 갈 수 없는 위치)

전형적인 BFS 문제이다. 도연이가 만날 수 있는 사람의 수를 구하면 된다.

2. 코드 분석

N, M = map(int, input().split())
campus = []
people = 0
visited = [[0 for _ in range(M)] for _ in range(N)]

캠퍼스의 크기인 N과 M을 입력받고, 캠퍼스의 정보들을 campus에 저장한다.

def bfs(graph, node_x, node_y,  visited):
    global people
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    if not visited[node_x][node_y]:
        visited[node_x][node_y] = 1

        for d in range(4):
            nx = node_x + dx[d]
            ny = node_y + dy[d]
            if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny]:
                if campus[nx][ny] == "P":
                    people += 1
                    bfs(campus, nx, ny, visited)
                elif campus[nx][ny] == "O":
                    bfs(campus, nx, ny, visited)

캠퍼스 내부에서 방문한 적이 없는 좌표라면 방문처리를 해준다.

if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny]:

그리고 해당 좌표에서 동서남북 좌표의 존재성과 방문여부를 확인해준다.

• 해당 좌표가 P라면, people에 1을 더하고,(만날 수 있는 사람 수 1 추가) bfs 함수를 호출해준다.
• 해당 좌표가 O라면, 그저 이동할 수 있는 좌표인 것이므로 bfs 함수를 호출해준다.

for i in range(N):
    campus.append(row := list(input().rstrip()))
    if "I" in row:
        row_I = i

bfs(campus, row_I, campus[row_I].index("I"), visited)
print(people) if people else print("TT")

N만큼 캠퍼스의 정보를 입력받고, 입력받은 정보에서 I가 등장하면 그 위치를 row_I로 저장해둔다.
I는 초기의 도연이의 위치이므로 bfs(campus, row_I, campus[row_I].index("I"), visited)으로 시작해준다.

people이 0이라면 "TT"를 출력하고, 아니라면 people을 출력한다.

3. 전체 코드

import sys
sys.setrecursionlimit(10**7)
input = open(0).readline

N, M = map(int, input().split())
campus = []
people = 0
visited = [[0 for _ in range(M)] for _ in range(N)]

def bfs(graph, node_x, node_y,  visited):
    global people
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    if not visited[node_x][node_y]:
        visited[node_x][node_y] = 1

        for d in range(4):
            nx = node_x + dx[d]
            ny = node_y + dy[d]
            if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny]:
                if campus[nx][ny] == "P":
                    people += 1
                    bfs(campus, nx, ny, visited)
                elif campus[nx][ny] == "O":
                    bfs(campus, nx, ny, visited)

for i in range(N):
    campus.append(row := list(input().rstrip()))
    if "I" in row:
        row_I = i

bfs(campus, row_I, campus[row_I].index("I"), visited)
print(people) if people else print("TT")