2 분 소요

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

문제 링크

성능 요약

메모리: 39488 KB, 시간: 740 ms

분류

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

제출 일자

2024년 3월 22일 09:37:09

문제 설명

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

도연이가 다니는 대학의 캠퍼스는 N x 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
import sys
input = sys.stdin.readline

N,M = map(int, input().split())
campus, temp = [], []
start=()

for i in range(N):
    temp = list(input().rstrip())
    for j in range(M): # 시작점 I 찾기
        if temp[j] == 'I':
            start = (i, j)
            break
    campus.append(temp)

    # down  right    up     left
d = [(1,0), (0,1), (-1,0), (0,-1)]
v = [[0]*M for _ in range(N)]
p = 0

queue = deque([start])
v[start[0]][start[1]] = 1 # 시작점 I 방문 표시
while(queue):
    x, y = queue.popleft()

    for dx, dy in d:
        nx, ny = x+dx, y+dy # 1칸 이동

        # 이동한 곳이 캠퍼스를 벗어나지 않고,
        if 0<=nx<N and 0<=ny<M:
            # 벽(X)이 아니고, 방문하지 않은 곳이면 방문
            if campus[nx][ny] != 'X' and not v[nx][ny]:
                queue.append((nx,ny))
                v[nx][ny] = 1

                # 사람을 만났으면 +1
                if campus[nx][ny] == 'P':
                    p += 1
print(p if p>0 else 'TT')

DFS, BFS로 접근할 수 있는 문제이다. 파이썬에 재귀호출이 1000번으로 제한되어 있다고해서 BFS로 문제를 풀었지만 나중에 알아보니 sys.setrecursionlimit()함수로 재귀호출 횟수를 늘릴 수 있었다.

temp에 캠퍼스 구성 문자열 한줄을 입력받고, 그 한줄에 대해서 for문으로 도연이가 있는 I의 인덱스를 찾는다. 그 후에 temp를 campus리스트에 추가한다. 입력과 시작점 파악이 끝나면 4방향을 한칸씩 이동하는 d리스트를 선언한다. 그리고 방문한 지점을 표시하는 v리스트와 만난 사람의 수를 저장하는 p를 같이 선언한다.

queue라는 deque리스트에 start시작점으로 초기화 해주고, v리스트에 시작점을 방문표시 해준다. 이제 BFS알고리즘을 이용하여 본격적인 도연이의 사람만나기가 시작된다. x,y에 queue에서 꺼낸 시작점 좌표값을 저장하고, for문으로 d에 저장된 4방향을 순회하며 1칸씩 이동을 하게된다. 만약 이동한 곳이 캠퍼스를 벗어나지 않고(if 0<=nx<N and 0<=ny<M:) 벽이 아님과 동시에 방문하지 않은 곳이면(if campus[nx][ny] != 'X' and not v[nx][ny]:)방문을 한다. 방문 과정은 queue에 이동을 마친 지점의 좌표를 추가해주고(다음 시작점의 위치) v리스트에 현재 위치의 방문표시를 해준다. 만약 이동한 곳에 사람이 있다?(if campus[nx][ny] == 'P':) 그러면 p에 1을 더해준다. 반복문이 끝난 후에 만난 사람의 수를 출력한다. 만난 사람이 없다면 TT를 출력한다.

댓글남기기

참고