[코드트리_IL]_비를피하기

숫자 0, 1, 2, 3로만 이루어진 n * n 격자에서 사람이 h명 겹치지 않게 서 있고, 비를 피할 수 있는 공간의 위치 m개가 주어졌을 때 각 사람마다 비를 피할 수 있는 가장 가까운 공간까지의 거리를 구하는 프로그램을 작성해보세요. 숫자 0은 해당 칸이 이동할 수 있는 곳임을, 숫자 1은 벽이 있어 해당 칸이 이동할 수 없는 곳임을 의미합니다. 숫자 2는 해당 칸에 사람이 서있음을 의미하고, 숫자 3은 해당 공간이 비를 피할 수 있는 공간임을 의미합니다. 사람은 상하좌우 인접한 곳으로만 움직 일 수 있으며 한 칸 움직이는 데 정확히 1초가 소요됩니다. 벽이 아닌 곳은 전부 이동이 가능합니다.

입력 형식

첫 번째 줄에 격자의 크기를 나타내는 n과 사람의 수를 나타내는 h 그리고 비를 피할 수 있는 공간의 수를 나타내는 m이 각각 공백을 사이에 두고 주어집니다.

출력 형식

n개의 줄에 걸쳐 각 행마다 각 칸에 대한 정보를 공백을 사이에 두고 출력합니다. 만약 해당 칸이 사람이 있던 칸이 아니라면 0을 출력하고, 사람이 있던 칸이라면 해당 사람이 비를 피할 수 있는 공간까지 가는데 걸리는 최소시간을 출력합니다. 만약 해당 위치에 있는 사람이 절대 비를 피할 수 없다면 -1을 출력합니다.

문제풀이

간단한 bfs문제이다.

방법1 . 해당 문제는 사람을 가리키는 x, y 위치에서 너비 우선 탐색을 진행하였을 때 3에 도달하는 depth값을

0으로 초기화되어있는 2차원배열의 x, y에 넣어주면 된다. 만약 3을 만나지 못한 경우엔 출발지점의 위치에 -1을 넣어준다.

 

방법 2. 2의 개수만큼 bfs를 진행해야 하지만 만약 3(shelter)의 위치를 que에 넣고 출발하여 2(person)를 목표로 가서 person에 누적 값을 저장하는 방법으로 풀면 bfs를 한 번만 진행할 수 있다.

 

# 0:이동, 1:벽, 2:사람, 3:비를피할수있는공간
from collections import deque
n, h, m = map(int,input().split())
graph = [list(map(int,input().split())) for _ in range(n)]

def in_range(x,y):
    return 0 <= x < n and 0 <= y < n
def can_go(x,y):
    return in_range(x,y) and graph[x][y] != 1 and not visited[x][y]
def bfs(x,y):
    que = deque()
    que.append((x,y))
    visited[x][y] = 1
    while que:
        dx,dy = que.popleft()
        for i in range(4):
            nx,ny = dx+dxs[i], dy+dys[i]
            if can_go(nx,ny):
                if graph[nx][ny] == 3 : #피를 피할 수 있는경우 2차원배열answer에 해당위치에 누적값 초기화
                    answer[x][y] = visited[dx][dy]
                    return True
                visited[nx][ny] = visited[dx][dy] + 1 # 3이아닌 can_go위치에 누적값초기화&방문처리
                que.append((nx,ny))
    answer[x][y] = -1   #3으로 리턴되지 않고 while문이 끝났으면 시작지점은 빠져나올 수 없는영역

dxs,dys = [1,-1,0,0],[0,0,1,-1]
answer = [[0]*n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if graph[i][j] == 2:
            visited = [[0]*n for _ in range(n)]
            bfs(i,j)

for i in answer:
    print(*i)