Algorithm & Data Structure/BOJ

[백준] 3055. 탈출 (Simulation, BFS)

남혁준 2020. 3. 31. 21:47

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

 

3055번: 탈출

문제 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다. 티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나

www.acmicpc.net

BFS를 활용하는 시뮬레이션 문제였습니다.

 

  • 고슴도치의 위치와 이동 시간을 담기 위해 따로 클래스를 만들어 사용했습니다.
  • visited배열도 고슴도치와 물 따로 사용하기위해 2개를 사용하였고,
  • 현재 고슴도치가 이동했던 위치를 담는 용도로 LinkedList를 사용했습니다.
    • 현재 LinkedList에 있는 위치정보를 고슴도치가 이동할때 Queue에 옮겨 담고, BFS적으로 이동가능한 다음 지점을 다시 LinkedList에 저장합니다.
  • 물의 전파와 고슴도치의 이동은 Queue를 사용해 BFS적으로 이동합니다.

전체 흐름은

  1. 고슴도치 안전검사
  2. 물 이동
  3. 고슴도치 이동

이 순서이며, 중간에 비버의 소굴에 도착하거나 안전하지 않으면 종료합니다.