BOJ_9376 [ 탈옥 ]

문제

https://www.acmicpc.net/problem/9376

 

 

실패 했던 이유

제출 했을 때 메모리 초과가 발생했다. 그 원인을 찾아보니 맵이 커지면 큐에 중복되서 좌표를 집어 넣어서 큐가 터져서 메모리 초과가 발생했던 것이다.

 

 

문제 해결 방법

문제에서 죄수2명과 상근이가 문을 최소로만 열고 탈옥을 해야되므로

각각 bfs를 돌려서 문을 최소로 열면서 탈옥하도록 구현을 한다.

이렇게 되면 죄수2명 상근 각각 이동 횟수 맵이 만들어지므로 총 3개 맵이 만들어진다.

3개 맵을 합쳐서 맵안에서 이동가능한 경로 중 최소값을 뽑아 내면 된다.

 

여기서 주의할 점

세명이 문 '#' 좌표에 모이는 곳을 처리하는 과정이다.

죄수나 상근이가 문을 열게되면 다른 두명은 그 문을 열 필요가 없기 때문에 그냥 이동이 가능하므로 3개 맵에 값을 합치면서 문인 경우에는 -2를 해주어야 된다.

 

 

 

 

소스 코드 보기

https://github.com/jokerKwu/BOJ_Algorithm/blob/master/BFS/boj_9376.cpp