[백준 5427] 불 (자바)

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

5427번: 불

 

난이도 : 골드 4

 

BFS를 이용해 풀었습니다.

2020/08/01 - [문제풀이/자바] - [백준 3055] 탈출 (자바)

[백준 3055] 탈출 (자바)

턴 시작 때 불을 번지게 하는 것이 이 문제와 유사하네요.

 

불이 번지게 하기 위해 불이 붙은 칸을 큐로 관리했습니다.

처음엔 리스트로 관리하다가 메모리 초과가 나서 큐로 바꿨습니다.

메모리 초과와 시간 초과 둘 다 맛봤는데요. 이것은 자료구조 문제가 아닌 로직이 잘못이었습니다.

 

불이 붙은 칸에서 불이 번지게 한 후에 다시 큐에 넣었습니다. 곰곰이 생각해보니 이미 불을 번지게 한 칸은 다시 쓸 일이 없었던 것이라 쓸모가 없었습니다. 덕분에 메모리, 시간 초과가 났었네요.

---

전역 변수 

int w, h = 문제에서 주어진 맵의 크기

char map[][] = 입력된 맵

Queue <Point> fire = 불의 위치를 저장하는 큐(불이 번져야 할 칸 - 원인)

int dx[], dy[] = 이동을 위한 배열

boolean visit[][] = 방문을 체크할 배열

StringBuilder sb = 출력 값

메소드

void main 

입력을 받고 상근이의 시작 위치를 x, y에 따로 저장합니다. 불의 위치는 fire에 넣어줍니다.

(excape 호출)

 

void escape

탈출을 시작합니다. 매 턴이 시작되기 전(상근의 이동 전) 불은 1칸씩 번집니다. 상근이 만약 지정된 맵의 크기를 벗어나는 위치를 가지게 된다면 탈출입니다.

(burn 호출)

 

void burn

불을 번지게 합니다. 

큐의 앞에는 번져야 할 위치들, 큐의 뒤에는 번진 위치들이 쌓여 있습니다.

그렇기 때문에 size로 번져야 할 위치들의 크기를 미리 가져옵니다.

불을 4방향으로 번지게 한 후에 큐에 넣습니다. 불이 번지는 곳은 빈칸인 '.', 상근이의 위치인 '@'입니다.

 

class Point

x, y 좌표를 저장하는 클래스입니다.