[백준 / BOJ] 1103 게임

문제

출처 : https://www.acmicpc.net/problem/1103

1103번: 게임

형택이는 1~9까지의 숫자와 구멍이 있는 직사각형 보드에서 게임을 한다.

보드의 1,1위치에 동전을 하나 올려놓고, 동전을 다음과 같이 움직인다.

- 동전이 놓인 위치에 있는 숫자만큼 위,아래,왼쪽,오른쪽 위치로 움직인다. (이 과정에서 구멍은 무시한다.)

- 동전이 이동한 위치에 구멍이 있거나 동전이 보드 밖으로 나가면 게임이 종료된다.

 

형택이가 동전을 최대 몇번 움직일 수 있는지 구하는 문제다.

 

풀이

그래프탐색에 메모이제이션을 적용해 푼 문제였다.

 

"현재위치에서 중복된 위치를 피해 최대로 움직일수있는 횟수"를 구하는 알고리즘을 기반으로 문제를 푸는데, 이를 모른다면

https://www.acmicpc.net/problem/1937와 같은 문제를 풀고 이 문제를 풀도록하자.

 

이 글을 읽는 사람들은 위 알고리즘을 이해하고있다고 가정하고 짧게 기술하겠다.

 

"현재위치에서 중복된 위치를 피해 최대로 움직일수있는 횟수" 는 바텀업으로 구현했고, (y,x)에서 갈수있는 모든 자식을 봐주며 해당 자식이 이미 다른 루트에 의해 방문되었다면 (이미 최댓값으로 업데이트 되어있을것이므로) 더 이상 들어가지않고 return한다.

이런식으로 최대로 갈수있는 경로를 찾아준다.

 

이제 무한히 동전을 옮길수있는경우(무한루프) 만 예외처리해주면 된다.

무한루프 예외처리에는 많은 방법이 있겠지만, 정점의 수가 적기때문에, 다소 무식한 방법을 사용해서 풀었다.

 

무한루프 체크 알고리즘은 다음과 같다.

- 하나의 정점(y,x)를 봐줄때마다 이전 정점의 위치를 같이 저장한다(beforeY, beforeX)

- 이때, y,x에서 beforeY,beforeX로 갈수있는 경로가 있는지 따로 체크해준다. 

- 갈수있다면, 어떤 경로로 가던 무한루프가 존재하므로 -1을 출력해준다.

- 무한루프 체크알고리즘도 중복을 피해 방문해야하는것에 주의하자

 

시간복잡도를 계산해보자. 

우선, 반복횟수를 생각해보면, 정점의 최대갯수가 2500개이므로, 중복을 피해 방문한다면, 2500번 정점을 방문한다.

무한루프를 체크할때 또한, 위와마찬가지로 최대 2500번 반복한다. 따라서, 최대 반복횟수는 2500^2이며,

시간복잡도는O((NM)^2)이 된다

 

주의할점이, 무한루프 체크 알고리즘을 실행하기전에 체크배열을 초기화 해주는 과정을 넣으면안된다.

(초기화 메소드를 넣을경우, NM^3번 반복하게 되어 시간초과가 나온다.)

초기화 하지않고 체크하는 방법을 넣자.(홀,짝으로 구분하거나 탐색횟수로 체크해주거나.)

 

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/1103%20%EA%B2%8C%EC%9E%84/main.cpp

devxb/JJUNalgo