[백준 2206번] 벽 부수고 이동하기 (java)

2206번: 벽 부수고 이동하기

 

처음에는 일반적인 너비우선탐색(BFS) 방법처럼 visited 배열을 2차원 배열로 만들어서 문제를 풀었으나, 

11%에서 틀렸다고 나왔다.

 

특정 위치(nr, nc)에 도착했을 때, 그 위치까지 도달하는 과정에서 벽을 한 번 부수고 도달했는지,

한 번도 부수지 않고 도달했는지 이 두가지 경우를 모두 고려해서 방문처리를 해야 한다.

 

따라서 visited 배열을 2차원 배열이 아닌 3차원 배열로 만들어서

1. 벽을 부수지 않고 방문한 경우 : visited[nr][nc][0]

2. 벽을 부수고 방문한 경우 : visited[nr][nc][1]

로 나누어서 방문처리를 하였다.

 

이 외의 다른 코드는 큐를 이용한 BFS 방식의 코드와 동일하게 해결하였다.