[BOJ] 20152 - Game Addiction

문제 출처

백준 20152 - Game Addiction

 

풀이

어떤 칸 x에 도달하는 최단 경로를 저장해주는 배열(map)과 x에 최단 경로로 도착할 수 있는 모든 경로들의 갯수를 저장해주는 배열(acc)을 따로 선언해주어야 합니다. 

 

- 큐에 데이터를 넣지 않는 경우

1. x에 도달했을 때 최단 경로가 아닐 경우

2. x가 이미 최단 경로가 갱신되어 있는 경우

 

즉, x에 최단 경로로 최초로 도달했을 때 방문 표시를 해주고 이후에 최단 경로로 도달하는 경로들은 x위치에 경로의 갯수만 저장해주는 것입니다. 

 

위와 같이 진행했을 때 목적지에 최단 경로로 도달할 수 있는 모든 경우의 수를 구할 수 있습니다. 그 이유는 다음과 같습니다.

큐는 선입선출(FIFO) 자료구조 입니다. 먼저 들어온 데이터가 먼저 나가는 자료구조이죠.

따라서 어떤 칸 x에 최단 경로로 도달할 수 있는 모든 경우가 x에 도달하고 나서야 x의 좌표가 큐에서 나오는 것입니다. 

 

코드

small-j/BOJ_Algorithm