[알고스팟/ALGOSPOT] 20. JUMPGAME

안녕하세요. 알고라파덕입니다.

20번 문제 JUMPGAME

이 JUMPGAME이란 문제는 동적계획법으로도 해결이 가능하고

DFS(깊이 우선 탐색기법)으로도 해결이 가능하고

BFS(너비 우선 탐색기법)으로도 해결이 가능합니다.

저는 BFS(너비 우선 탐색기법) 을 보여 드리겠습니다.

문제의 요점은 게임판의 숫자만큼 행과 열로 이동을 하여 도착지점(N,N)에 

도착 할 수 있는가 없는가를 구하는 문제입니다.

ex) 

3

2 1 1

1 1 2

2 1 0

이런 입력 데이터에서는 (1, 1)에서 오른쪽으로 2칸 이동하는 경로는 (2, 3)에 도착해 불가능하지만,

(1,1)에서 아래쪽으로 2칸 이동하는 경로는 (1, 1) -> (3, 1) -> (3, 3) (3, 3)에 도착해 가능합니다.

그래서 YES를 출력합니다.

JUMPGAME

출처 : https://algospot.com/judge/problem/read/JUMPGAME

문제 정보

• • 문제 ID
  • 시간 제한
  • 메모리 제한
  • 제출 횟수
  • 정답 횟수 (비율)
• • JUMPGAME
  • 3000ms
  • 65536kb
  • 3014
  • 1102 (36%)
• • 출제자
  • 출처
  • 분류
• • JongMan
  • 알고리즘 문제 해결 전략
  • 보기

문제

땅따먹기를 하다 질린 재하와 영훈이는 땅따먹기의 변종인 새로운 게임을 하기로 했습니다. 이 게임은 그림과 같이 n*n 크기의 격자에 각 1부터 9 사이의 정수를 쓴 상태로 시작합니다. 각 차례인 사람은 맨 왼쪽 윗 칸에서 시작해 외발로 뛰어서 오른쪽 아래 칸으로 내려가야 합니다. 이 때 각 칸에 적혀 있는 숫자만큼 오른쪽이나 아래 칸으로 움직일 수 있으며, 중간에 게임판 밖으로 벗어나면 안 됩니다.

균형을 잃어서 다른 발로 서거나 넘어져도 게임에서 집니다만, 재하와 영훈이는 젊고 활기차기 때문에 외발로 뛰어다니는 것은 아무것도 아닙니다. 다만 걱정되는 것은 주어진 게임판에 시작점에서 끝점으로 가는 방법이 존재하지 않을 수도 있다는 것입니다. 예를 들어 그림 (a)의 게임판에서는 사각형으로 표시된 칸들을 통해 끝에 도달할 수 있지만, 숫자가 하나 바뀐 그림 (b)에서는 그럴 수가 없습니다.

게임판이 주어질 때 왼쪽 위의 시작점에서 오른쪽 아래의 시작점에 도달할 수 있는 방법이 있는지 확인하는 프로그램을 작성하세요.

입력

입력의 첫 줄에는 테스트 케이스의 수 C(C <= 50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 격자의 크기 n(2 <= n <= 100)이 주어지고, 그 후 n줄에 각 n개의 숫자로 왼쪽 위부터 각 칸에 쓰인 숫자들이 주어집니다. 오른쪽 아래 있는 끝 점 위치에는 0이 주어집니다.

출력

각 테스트 케이스마다 한 줄로, 시작점에서 끝 점으로 도달할 수 있을 경우 "YES"를, 아닐 경우 "NO"를 출력합니다. (따옴표 제외)

예제 입력

2
7
2 5 1 6 1 4 1
6 1 1 2 2 9 3
7 2 3 2 1 3 1
1 1 3 1 7 1 2
4 1 2 3 4 1 2
3 3 1 2 3 4 1
1 5 2 9 4 7 0
7
2 5 1 6 1 4 1
6 1 1 2 2 9 3
7 2 3 2 1 3 1
1 1 3 1 7 1 2
4 1 2 3 4 1 3
3 3 1 2 3 4 1
1 5 2 9 4 7 0 

예제 출력

YES
NO

생각해야할 점

이동을 어떤 식으로 해야 하는가.

이동은 현재 위치에서 자신의 칸의 수만큼 아래로 이동 또는 오른쪽으로 이동이 있습니다.

현재 위치의 인덱스 번호를 (row, col) 두 변수로 저장을 하였다면

아래로 이동할 때의 위치 : (row + Data[row][col], col)

오른쪽으로 이동할 때의 위치 : (row, col + Data[row][col])

모든 경우의 수를 다 탐색을 해야한다.

모든 경우의 수를 탐색 할 때 시간에 민감해지게 되는데 이것을 어떻게 처리하느냐가 중요합니다.

DFS(깊이 우선 탐색기법)이나 동적계획법을 사용할 때에는 메모이제이션 기법을 이용하여 

현재의 위치에서 이동했을 때의 도착 가능성 여부를 저장합니다.

BFS(너비 우선 탐색기법)을 이용할 때에는 문제의 목적이 가장 빠른 경로나 경로의 개수를 출력하는 것이 아니라

도착 여부를 구하는 것이기 때문에 BFS 탐색 기법을 이용하여 도착할 경우 YES를 출력하고 바로 끝나게 됩니다.

소스 코드 확인

초기 설정

Chk[i][j] = 0;

한번 가본 곳은 1로 표시해주어 갔던 길을 다시 가지 않는다.

q[1][1] = q[2][1] = 1;

int f=0, r=1;

int row, col, sw=0;

queue배열의 첫 번째 열은 출발점 위치로 1, 1을 넣어준다. (q의 1행은 행 번호, 2행은 열 번호를 저장한다.)

큐의 머리와 꼬리 (1, 0)

sw는 도착을 할 수 있는지 못 하는지 알 수 있는 변수로 1일 경우 도착이 된다.

입력 부분

for(int i = 1; i<=N; i++)

{

for(int j=1; j<=N; j++)

{

scanf("%d", &Data[i][j]);

Chk[i][j] = 0;

}

}

Chk배열을 초기화 한다.

해결 부분

while(f < r)

{

row = q[1][++f];

col = q[2][f];

if(row == N && col == N) 

{

sw = 1;

break;

}

if(row + Data[row][col] <= N && Chk[row+Data[row][col]][col] == 0)

{

q[1][++r] = row + Data[row][col];

q[2][r] = col;

Chk[row+Data[row][col]][col] = 1;

}

if(col + Data[row][col] <= N && Chk[row][col+Data[row][col]] == 0)

{

q[1][++r] = row;

q[2][r] = col + Data[row][col];

Chk[row][col+Data[row][col]] = 1;

}

}

if(sw == 1) printf("YES\n");

else printf("NO\n");

꼬리를 하나 올리면서 다음 행 번호와 열 번호를 받는다.

그 위치에서 먼저 아래로 갈 수 있는지 확인하고

(점프 게임 맵을 벗어나지 않고(row + Data[row][col] <= N) 

가본적이 없는지(Chk[row+Data[row][col]][col] == 0)

다음 가야할 위치로 기억해둔다.

(q[1][++r] = row + Data[row][col];

q[2][r] = col;)

가본 적이 있다고 표시를 한다.

(Chk[row+Data[row][col]][col] = 1;)

sw == 0인지 1인지 확인하여

(sw == 1일 경우) 도착하는 방법이 있기 때문에 YES 출력

(sw == 0일 경우) 도착하는 방법이 없기 때문에 NO 출력

#include <iostream>

using namespace std;

void INPUT();

int q[3][10010];

int Data[110][110] = { 0 }, Chk[110][110] = { 0 };

int main()

{

int T;

scanf("%d", &T);

while(T >= 1)

{

--T;

INPUT();

}

return 0;

}

void INPUT()

{

int N;

scanf("%d", &N);

for(int i = 1; i<=N; i++)

{

for(int j=1; j<=N; j++)

{

scanf("%d", &Data[i][j]);

Chk[i][j] = 0;

}

}

q[1][1] = q[2][1] = 1;

int f=0, r=1;

int row, col, sw=0;

while(f < r)

{

row = q[1][++f];

col = q[2][f];

if(row == N && col == N) 

{

sw = 1;

break;

}

if(row + Data[row][col] <= N && Chk[row+Data[row][col]][col] == 0)

{

q[1][++r] = row + Data[row][col];

q[2][r] = col;

Chk[row+Data[row][col]][col] = 1;

}

if(col + Data[row][col] <= N && Chk[row][col+Data[row][col]] == 0)

{

q[1][++r] = row;

q[2][r] = col + Data[row][col];

Chk[row][col+Data[row][col]] = 1;

}

}

if(sw == 1) printf("YES\n");

else printf("NO\n");

}

감사합니다.