[백준] G2 1103번 게임 (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

1103번: 게임

[문제] 

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

일단 보드의 가장 왼쪽 위에 동전을 하나 올려놓는다. 그다음에 다음과 같이 동전을 움직인다.

1. 동전이 있는 곳에 쓰여 있는 숫자 X를 본다.
2. 위, 아래, 왼쪽, 오른쪽 방향 중에 한가지를 고른다.
3. 동전을 위에서 고른 방향으로 X만큼 움직인다. 이때, 중간에 있는 구멍은 무시한다.

만약 동전이 구멍에 빠지거나, 보드의 바깥으로 나간다면 게임은 종료된다. 형택이는 이 재밌는 게임을 되도록이면 오래 하고 싶다.

보드의 상태가 주어졌을 때, 형택이가 최대 몇 번 동전을 움직일 수 있는지 구하는 프로그램을 작성하시오.

[입력]

줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 H이다. 가장 왼쪽 위칸은 H가 아니다. H는 구멍이다.

[출력]

첫째 줄에 문제의 정답을 출력한다. 만약 형택이가 동전을 무한번 움직일 수 있다면 -1을 출력한다.

 

---

[풀이]

1. 입력을 받아준다.

2. 무한루프를 도는 지 확인을 위한 플래그를 만들어준다.

3. DFS를 탐색하면서 DP에 현재 이동 횟수를 저장한다.

4. 이미 방문한 곳이라면 무한루프 플래그를 True로 만들어준다.

5. 이동할 곳이 범위를 벗어나거나 구멍이라면 다음 탐색을 진행한다.

6. 방문 처리를 하고 DFS 추가 탐색을 하고 이후 방문 처리를 취소한다.

7. 모든 탐색이 끝나고 나면 무한루프 플래그에 따라 최댓값 또는 -1을 출력해준다.

[접근]

1. 처음 문제를 봤을때는 DFS로 탐색하면서 조건에 맞는 경우에 결과를 출력해주면 되겠다고 생각하였는데 방문처리를 하는 것에서 문제가 발생한다는 것을 알았다.

2. 해당 문제를 해결하기 위해 DP를 사용해 값을 저장해주고 방문처리를 다시 취소해주는 방식을 사용하였다.

[오답 코드]

import java.io.*;
import java.util.*;

public class Main {
	static int n, m;
	static char[][] map;
	static boolean[][] visited;
	static int ans;
	
	static int[] dr = {0, 0, -1, 1};
	static int[] dc = {-1, 1, 0, 0};

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		map = new char[n][m];
		visited = new boolean[n][m];
		
		// 값 입력
		for (int i = 0; i < n; i++) {
			String str = br.readLine();
			for (int j = 0; j < m; j++) {
				map[i][j] = str.charAt(j);
			}
		}
		
		// 시작점에서 이동횟수 1로 잡고 시작
		dfs(0, 0, 1);
		
		// 결과 출력
		System.out.println(ans);
	}
	
	public static void dfs(int x, int y, int move) {
		// 이미 방문한 곳에 도착이 가능하면 무한번 이동 가능
		if (visited[x][y]) {
			System.out.println(-1); // -1 출력하고 종료
			System.exit(0);
		}
		
		visited[x][y] = true; // 방문처리
		
		// 현재 위치값을 숫자로 변환
		int k = Integer.parseInt(map[x][y] + "");
		
		// 4방 탐색
		for (int i = 0; i < 4; i++) {
			int nx = x + (k * dr[i]);
			int ny = y + (k * dc[i]);
			
			// 범위를 벗어나거나 구멍인 곳
			if (nx < 0 || ny < 0 || nx >= n || ny >= m || map[nx][ny] == 'H') {
				ans = Math.max(ans, move); // 최고 이동 횟수
				continue;
			}
			
			// 이동횟수를 증가시키고 추가 탐색
			dfs(nx, ny, move + 1);
		}
	}
}

 

[정답 코드]

import java.io.*;
import java.util.*;

public class Main {
	static int n, m;
	static char[][] map;
	static int[][] dp;
	static boolean[][] visited;
	static int ans;
	static boolean inf;
	
	static int[] dr = {0, 0, -1, 1};
	static int[] dc = {-1, 1, 0, 0};

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		map = new char[n][m];
		dp = new int[n][m];
		visited = new boolean[n][m];
		
		// 값 입력
		for (int i = 0; i < n; i++) {
			String str = br.readLine();
			for (int j = 0; j < m; j++) {
				map[i][j] = str.charAt(j);
			}
		}
		
		inf = false; // 무한루프 확인용 플래그
		visited[0][0] = true; // 시작지점 방문처리
		// 시작점에서 이동횟수 1로 잡고 시작
		dfs(0, 0, 1);
		
		// 결과 출력
		if (!inf)
			System.out.println(ans);
		else
			System.out.println(-1);
	}
	
	public static void dfs(int x, int y, int move) {
		// 최고값 갱신
		ans = Math.max(ans, move);
		// 현재 위치를 지금까지 이동 횟수로 저장
		dp[x][y] = move;
		
		// 현재 위치값을 숫자로 변환
		int k = Integer.parseInt(map[x][y] + "");
		
		// 4방 탐색
		for (int i = 0; i < 4; i++) {
			int nx = x + (k * dr[i]);
			int ny = y + (k * dc[i]);
			
			// 범위를 벗어나거나 구멍인 곳
			if (nx < 0 || ny < 0 || nx >= n || ny >= m || map[nx][ny] == 'H') {
				continue;
			}
			
			// 이미 방문한 곳에 도착이 가능하면 무한번 이동 가능
			if (visited[nx][ny]) {
				inf = true; // -1 출력하고 종료
				return;
			}
			
			// 도착한 지점이 이미 이전에 저장된 횟수보다 많으면 탐색을 할 필요가 없음
			if (dp[nx][ny] > move)
				continue;
			
			// 방문 처리
			visited[nx][ny] = true;
			// 이동횟수를 증가시키고 추가 탐색
			dfs(nx, ny, move + 1);
			// 다른 방향 탐색에서 문제가 되지 않도록 다시 방문 처리 제거
			visited[nx][ny] = false;
		}
	}
}