[Baekjoon] 1890_점프

Silver I

문제(출처: https://www.acmicpc.net/problem/1890)

---

< 점프 >

 

문제 풀이 

 

게임 판의 정보를 저장하는 배열, 이동 위치를 표시하는 배열, 경로 수를 구하는 배열 총 3개의 배열을 사용해서 문제를 해결했다. 

 

만약 문제에서 주어진 예제로 설명해 보자.

4
2 3 3 1
1 2 1 3
1 2 3 1
3 1 1 0

와 같이 예제가 주어졌다면 이동 위치를 표시하는 배열은 다음과 같다.

 

경로 수를 구하는 배열은 다음과 같다.

 

각 경로는 같은 이동 번호인 경우가 아니라면 따로 관리한다. 위에서 4번 이동하여 오른쪽 아래로 오는 경우가 2가지였고 5번 이동해서 오른쪽 아래 도착하는 경우가 1가지이므로 먼저 도착한 경우의 수를 따로 저장해 두고 1로 저장한다.

 

반복문을 사용해서 이동 번호로 탐색하면 아직 모든 게임 판을 순환하지 않았는데 새로운 값으로 갱신될 수 있으므로 ArrayList를 사용하여 값을 저장해 뒀다가 모든 탐색이 끝난 후 한 번에 값을 교체한다.

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class _1890_ { // 점프

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int n = Integer.parseInt(bf.readLine());

		int arr[][] = new int[n][n];
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(bf.readLine());
			for (int j = 0; j < n; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		long move[][] = new long[n][n];
		long count[][] = new long[n][n];

		move[0][0] = 1;
		count[0][0] = 1;
		long idx = 1;
		boolean flag = false;
		long result = 0;
		ArrayList<long[]> list = new ArrayList<>();

		while (true) {
			flag = false;
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if (i == n - 1 && j == n - 1) {
						continue;
					}
					if (move[i][j] == idx) {
						if (arr[i][j] == 0) {
							continue;
						}
						flag = true;
						if (j + arr[i][j] < n) {
							list.add(new long[] { i, j + arr[i][j], count[i][j] });
						}
						if (i + arr[i][j] < n) {
							list.add(new long[] { i + arr[i][j], j, count[i][j] });
						}
					}
				}
			}
			for (long[] temp : list) {
				int a = (int) temp[0];
				int b = (int) temp[1];
				if (move[a][b] != idx + 1) {
					if (a == n - 1 && b == n - 1) {
						result += count[a][b];
					}
					count[a][b] = 0;
				}
				move[a][b] = idx + 1;
				count[a][b] += temp[2];
			}
			idx++;
			list.clear();
			if (!flag) {
				break;
			}
		}
		System.out.println(result + count[n - 1][n - 1]);
	}
}

변수)
n : 게임판의 크기
arr : 게임판 정보
move : 이동 위치 번호 표시
count : 경우의 수 표시
idx : 이동 번호
flag : 이동할 것이 남아있는지 여부
result : 가장 오른쪽 아래 칸으로 도착하는 경로의 개수 저장
list : 값 교체를 위한 ArrayList

 

move 배열을 전체 순환하면서 현재 이동 번호와 같다면 오른쪽 또는 아래로 이동 가능한지 판단 후 이동 가능하다면 list에 [x 좌표, y 좌표, 경로 수 ]를 저장한다. move 배열 전체 순환이 끝나면 값을 교체하기 위해 list를 순환한다. 이때, 이동할 곳에 idx+1 값이 아니라면 이미 지나간 경로의 수와 겹치지 않기 위해 값을 초기화한다. 만약 이동할 위치가 가장 오른쪽 아래라면 정답에 포함시켜야 하므로 result에 값을 저장한다. move와 count에 새로운 값을 저장한다.

더 이상 이동할 곳이 없다면 종료한 후에 result+count [n-1][n-1]을 출력한다.

---

---