(JAVA) 백준 3055번 : 탈출

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

3055번: 탈출

 

 

시뮬레이션 문제.

 

 

고슴도치를 이리저리 움직여서 동굴에 들어갈 수 있는 최단 시간을 구하는 문제.

 

 

물, 굴, 돌 이 추가되서 꽤 난이도가 있어보이긴 하지만

 

문제를 유심히 살펴보면

 

전부 고슴도치가 이동할 수 없다는 공통점이 있다.

** 굴은 최종 목적지 이기 때문에 바로 판별할 수 있다.

 

 

또 다른 핵심은

 

여기서 보면

" 물이 찰 예정인 칸으로 이동할 수 없다. " 고 한다.

 

이는 즉 시간이 1초 지났을 때 고슴도치가 이동할 수 없는 곳은

물이 차 있는 곳 + 물의 상하좌우(물이 찰 예정인 칸) 인 곳 + 돌 + 굴 이다.

 

 

마지막으로

시간 초과와 메모리 초과 오류를 방지하기 위해

 

고슴도치가 지나온 자리는 이동할 수 없다 고 판단하는 것이 좋다. (boolean 변경)

 

 

물론 고슴도치가 이전 자리로 되돌아갈 순 있지만

 

다른 DFS나 BFS에서와 마찬가지로

 

최소 시간을 구할 경우 되돌아간다는 것은 이미 최소가 아니기 때문이다.

 

 

 

매커니즘

---

 

초기 설정 값

 

-> 좌표를 표현하기 위해 별도의 클래스를 만들어 사용했다.

*** int[2] 변수를 사용해도 무방하다. 가독성을 위해 클래스를 만들었다.

 

-> 입력값을 담는 char[][]

 

-> 이동 가능 여부를 판단하는 boolean[][]

 

-> 상 - 좌 - 하 - 우 순서대로 좌표 값을 바꾸는 moveX int[], moveY int[]

 

-> 고슴도치가 이동해있는 위치 좌표를 담은 Queue<Point>

 

-> 다음 시간에 물이 흐를 것으로 예상되는 위치 좌표를 담은 Queue<Point>

 

 

 

 

 

알고리즘

1) 고슴도치 시작 지점, 도착 지점(동굴) 좌표 얻음.

 

 

2) 초기 물 좌표 Queue 저장

 

 

3) 초기 고슴도치 시작 좌표 Queue 저장

 

 

4) 0초부터 시작. While(True)

 

*** 물 셋팅

4-1) 물 좌표 Queue에서 하나씩 꺼내며 상하좌우로 물 이동 예상 좌표를 파악한 후 boolean[][] 변경.

 

4-2) 예상 좌표를 새로운 물 좌표 Queue에 넣음

 

4-3) 기존 물 좌표 Queue가 빈다면, 새로운 물 좌표 Queue를 기존 물 좌표 Queue로 복사.

 

 

*** 고슴도치 이동

4-4) 고슴도치 위치 Queue에서 하나씩 꺼내며 상하좌우로 고슴도치 이동 가능 여부를 파악

 

4-5) 도착 지점으로 이동 가능한 경우 현재 시간 + 1 리턴.

 

4-6) 이동 가능한 경우 boolean[][] 변경 후 4-2) 와 동일하게 진행

 

4-7) 시간 1초 증가시킨 후 4) 반복

 

 

5) 결과 출력

 

**** 4) While문에서 반드시 고슴도치가 이동할 수 있는 경우가 없을 때를 따져봐야 한다. (고슴도치 Queue Empty)

**** 그래서 없다면 "KAKTUS" 출력.

 

 

 

감사합니다!

 

다들 화이팅하시고

 

좋은 하루 되세요~! ^_^

 

 

소스코드

---