BOJ 9376(탈옥)

작성일 | In

탈옥

  • * : 벽
  • # : 문
  • . : 빈칸
  • $ : 죄수
  • 탈옥을 한다는 것은 죄수가 지도를 벗어난다는 것을 의미

  • 열어야 하는 문의 최소 개수를 구하는 것.

  • 가중치를 생각해볼까?
  • 어떤 칸에서 문으로 간다 -> 가중치 1
  • 어떤 칸에서 빈칸으로 간다 -> 문은 열필요 없어 -> 0
  • 즉 가중치가 0과 1이 나온다.

  • BFS 이용해서 풀 수 있다.

  • 빈 칸, 벽, 문으로 이루어진 지도가 주어진다.
  • 두 죄수가 탈옥하기 위해서 열어야 하는 문의 최소 개수를 구하는 문제
  • 까다로운 이유는 두 죄수다. 시작점이 두 개인 경우다.
  • 그림에서 봤듯이, 두 죄수가 같은 곳을 지나면 두번 더해주면 지나고 한번만 문제의 정답에 더해줘야 한다.
  • 이게 이 문제를 어렵게 만드는 조건이다.

단계별 풀이

  • 죄수가 한명만 있을 때, 이동하는 경우를 생각해보자.
  • 시작점 한개. 도착점은 어디 ? -> 그냥 0,0으로 해도 된다.
  • 0과 1이 나오는 그래프 이고, 1이나오는 경우 문, 0은 빈칸
  • 어차피 밖은 모두 빈칸이기 때문에, 가중치가 0이다. 따라서 어떻게든지 0,0으로 올 수 밖에 없고 그 때는 0이니까 상관 없다.
  • 시작점이 하나이고 도착점이 하나일 때, BFS로 풀 수 있다.
  • 문제는 시작점이 두개라는 것이다.
  • 시작점이 두 개일 때, 어떻게 처리 ?
  • 간단한 방법이 있다 -> 요약을 해보면 이 문제는 죄수 1과 죄수 2가 탈옥을 시작해서 어떤 한 곳에서 만난 다음에, 도착점으로 가는 것과 같은 모양을 만들게 된다.

  • 예시 그림은 가운데에서 만나서 함께 이동한다.

  • 그렇다면 함께 만나는 걸 어떻게 처리 ?
  • BFS의 시간복잡도는 NM
  • 문제는 이 칸이 어디인지 알 수 없다.
  • 우리가 사용하는 BFS -> 시작점 하나 -> BFS 나머지
  • NM개가 정해질 때마다 BFS를 3번 돌아야 하니까-> BFS를 NM번 해야지 풀 수 있다.

  • BFS의 시간복잡도는 NM이니까 총 NM^2이 나온다.

  • 이 문제를 BFS 3번만 하게 바꿀 수 있다.

  • 1 -> 어딘가, 2- > 어딘가.
  • 도착에서 어딘가로 가는 것으로 바꿀 수 있다.

  • 양 방향 그래프이고, A->B, B->A로 가는게 항상 같게 나오기 때문이다.

  • 시작점이 3개이고, 도착점이 하나인데 각각이 다 별개의 BFS가 된다.

  • 예외 -> 모이는 칸이 문이였다고 하면, 문은 한번만 열면 되므로 정답에서 2를 빼주면 된다. 왜 2를 빼냐면 세개가 한 곳에서 만났으니까, 가중치가 한번 더해져야 하기 때문이다.
from collections import deque
dx = [0,0,1,-1]
dy = [1,-1,0,0]
def bfs(a, x, y): # bfs를 함수로 제작. a가 지도, x행 y열에서 탐색 시작
    n = len(a)
    m = len(a[0])
    dist = [[-1]*m for _ in range(n)] # 배열 -1로 초기화
    q = deque() # 0일 때는 앞에, 1일 때에는 뒤에 넣는다 덱 용
    q.append((x,y))
    dist[x][y] = 0 # x,y 큐에 넣어주고 시작
    while q:
        x,y = q.popleft()
        for k in range(4):
            nx,ny = x+dx[k], y+dy[k]
            if 0 <= nx < n and 0 <= ny < m and dist[nx][ny] == -1 and a[nx][ny] != '*': # 범위 체크, -1이어야 하고(이동 안한 곳), 벽이면 이동불가,
                if a[nx][ny] == '#': #
                    dist[nx][ny] = dist[x][y] + 1 # 문을 열어야 하니 +1
                    q.append((nx,ny)) # 나중에 처리해야하니까 큐의 뒤쪽에 넣는다
                else: # 문이 아닌경우는 이동해야하니까
                    dist[nx][ny] = dist[x][y]
                    q.appendleft((nx,ny)) # 큐의 앞쪽에 넣어준다
    return dist

t = int(input())
for _ in range(t):
    n,m = map(int,input().split())
    a = ['.'+input()+'.' for _ in range(n)]
    n += 2
    m += 2
    a = ['.'*m] + a + ['.'*m]
    d0 = bfs(a, 0, 0) # 0,0에서 시작해서 가는 모든 경로
    x1=y1=x2=y2=-1
    for i in range(n):
        for j in range(m):
            if a[i][j] == '$':
                if x1 == -1:
                    x1,y1 = i,j
                else:
                    x2,y2 = i,j
    d1 = bfs(a,x1,y1) # 죄수 1에서 시작해서 가는 모든 경로
    d2 = bfs(a,x2,y2) # 죄수 2에서 시작해서 가는 모든 경로
    ans = n*m

    for i in range(n):
        for j in range(m):
            if a[i][j] == '*': # 벽이면 건너뛰고
                continue
            cur = d0[i][j] + d1[i][j] + d2[i][j] # 세개를 합쳐주면 총 문을 몇 개 열어야 하는지 알 수 있다.
            if a[i][j] == '#':
                cur -= 2 # 예외처리
            ans = min(ans,cur)
    print(ans)
  • 만나는 위치가 도착점과 같다면 ? -> 전혀 문제가 안된다. 도착점에서 도착점에서 가는건 0이니까 결과 영향 x

참고자료 codeplus

0%