[Silver II] 헌내기는 친구가 필요해 - 21736

문제 링크

성능 요약

메모리: 36692 KB, 시간: 356 ms

분류

너비 우선 탐색, 깊이 우선 탐색, 그래프 이론, 그래프 탐색

제출 일자

2024년 10월 19일 20:00:14

문제 설명

2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 싶다.

도연이가 다니는 대학의 캠퍼스는 N×M 크기이며 캠퍼스에서 이동하는 방법은 벽이 아닌 상하좌우로 이동하는 것이다. 예를 들어, 도연이가 (x, y)에 있다면 이동할 수 있는 곳은 (x+1, y), (x, y+1), (x−1, y), (x, y−1)이다. 단, 캠퍼스의 밖으로 이동할 수는 없다.

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

입력

첫째 줄에는 캠퍼스의 크기를 나타내는 두 정수 N (1≤N≤600), M (1≤M≤600)이 주어진다.

둘째 줄부터 N개의 줄에는 캠퍼스의 정보들이 주어진다. O는 빈 공간, X는 벽, I는 도연이, P는 사람이다. I가 한 번만 주어짐이 보장된다.

출력

첫째 줄에 도연이가 만날 수 있는 사람의 수를 출력한다. 단, 아무도 만나지 못한 경우 TT를 출력한다.

풀이

from collections import deque

n, m = map(int, input().split())
campus = [list(input()) for _ in range(n)]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
count = 0


def bfs(campus, a, b):
    global count
    queue = deque()
    queue.append((a, b))
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y
            if nx < 0 or nx >= n or ny < 0 or ny >= m or campus[nx][ny] == "X":
                continue
            if campus[nx][ny] == "P":
                count += 1
            campus[nx][ny] = "X"
            queue.append((nx, ny))


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

print(count if count else "TT")

그냥 문제를 봤을 때 bfs나 dfs로 풀어야겠다는 생각이 들었다.

bfs가 좀 더 편하다는 생각이 들어서 bfs 알고리즘을 사용하여 문제를 풀었다.

이동은 상하좌우로만 갈 수 있기 때문에 dx, dy를 위와 같이 했다.

캠퍼스를 하나씩 돌다가 `I`가 나온다면 bfs를 돌도록 했다.

bfs 알고리즘으로는 범위를 벗어나고, `X`는 벽이기 때문에 이에 해당하는 것들은 건너뛰어 준다.

`P`를 만난다면 카운트를 세어준다. 이외에는 다시 방문을 하면 안되기 때문에 `X`로 치환해주면서 bfs를 계속 돌도록 했다.

import sys
sys.setrecursionlimit(10 ** 6)

n, m = map(int, input().split())
campus = [list(input()) for _ in range(n)]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
count = 0


def dfs(campus, x, y):
    global count
    for i in range(4):
        nx = dx[i] + x
        ny = dy[i] + y
        if nx < 0 or nx >= n or ny < 0 or ny >= m or campus[nx][ny] == "X":
            continue
        if campus[nx][ny] == "P":
            count += 1
        campus[nx][ny] = "X"
        dfs(campus, nx, ny)


for i in range(n):
    for j in range(m):
        if campus[i][j] == "I":
            dfs(campus, i, j)

print(count if count else "TT")

dfs로도 한 번 풀어보고 싶다는 생각이 들어서 dfs로도 풀었다.

이건 그냥 알고리즘은 다 동일하고 큐를 사용하지 않고 재귀를 할 수 있도록 했다.