[Java] 백준 1103 게임

unzinzanda·2023년 3월 30일
1

백준

목록 보기
2/6
post-thumbnail

백준 1103 게임

풀이

(0, 0)부터 탐색을 시작하여 도착하는 칸마다 사방 탐색을 진행해야 합니다. 이 때, 방문했던 칸에 대한 처리를 visited 배열을 통해야 하는데 boolean 배열 대신 int 배열을 사용하여 visited에 대한 처리와 최대 움직인 횟수를 한 배열에 저장하였습니다.
그 방법은 다음과 같습니다.

3 7
3942178
1234567
9123532

이러한 입력이 주어졌을 때 visited 배열의 초기 모습은

-1로 초기화되어 있습니다. -1은 아직 방문하지 않은 칸임을 의미합니다.
(0, 0)부터 탐색을 진행하면 방문한 배열은 일단 0으로 값을 변경합니다.


몇 번의 이동으로 visited 배열이 이와 같은 모습이 되었을 때, (0, 6)은 네 방향 중 어디로도 이동할 수 없으므로 처음 return이 발생합니다.이 때, 해당 자리에 최대 움직인 횟수를 기록합니다. visited 배열엔 다음과 같은 모습으로 최대 움직인 횟수가 기록 됩니다.

각 자리마다 사방 탐색을 진행하였을 때 가장 이동을 많이 한 횟수만이 칸에 저장되기 때문에 (0, 3)의 경우, 아래로 갔을 때 4회, 왼쪽으로 갔을 때 2회, 오른쪽으로 갔을 때 2회 이동이 가능하므로 최댓값인 4가 기록되는 모습을 볼 수 있습니다.


추가적으로 이 문제에 주어진 조건으로 무한히 이동할 수 있다면 -1을 출력하라는 조건이 있습니다. 이는 경로 탐색 중 cycle이 발생하거나 바로 직전에 탐색한 칸으로 돌아올 수 있다면 -1을 출력하라는 것으로 해석할 수 있습니다. 따라서 이 코드에선 경로를 탐색하던 중 visited값이 0인 칸을 만나면 cycle이 생긴 것이고 -1을 출력하면 됩니다. 현재 탐색에서 visited가 0이 아닌 칸은 탐색이 종료된 지점이고 현재의 경로로 다시 돌아온다고 보장할 수 없기 때문입니다.


이러한 내용을 코드로 짜면 다음과 같습니다.

코드

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

//백준 1103 게임
public class b1103 {
	static int N, M;
	static int board[][];
	static int visited[][];
	static boolean cycle;
	static int dx[] = {1, -1, 0, 0};
	static int dy[] = {0, 0, 1, -1};
	
	public static int dp(int x, int y) {
		if(x >= 0 && x < N && y >= 0 && y < M) {
			if(visited[x][y] == -1) {
				int cal = 0;	// 사방 탐색을 하고 사방 중 최대로 많이 이동한 횟수
				if(board[x][y] == -1) {
					return 0;
				}
				else {
					visited[x][y] = 0;	// 일단 방문 처리
					
					for(int i = 0;i < 4;i++) {
						int nx = x + dx[i] * board[x][y];
						int ny = y + dy[i] * board[x][y];
						
						cal = Math.max(cal, dp(nx, ny) + 1);
					}
					return visited[x][y] = cal;
				}
			} else if(visited[x][y] == 0) {
				cycle = true;
			} else {
				return visited[x][y];
			}
		}
		return 0;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str[] = br.readLine().split(" ");
		
		N = Integer.parseInt(str[0]);
		M = Integer.parseInt(str[1]);
		board = new int[N][M];
		visited = new int[N][M];
		for(int i = 0;i < N;i++) Arrays.fill(visited[i], -1);
		
		// H : -1로 표시
		for(int i = 0;i < N;i++) {
			str = br.readLine().split("");
			for(int j = 0;j < str.length;j++) {
				if(str[j].equals("H")) board[i][j] = -1;
				else board[i][j] = Integer.parseInt(str[j]);
			}
		}
		
		dp(0, 0);
		
		if(cycle) System.out.println(-1);
		else System.out.println(visited[0][0]);
	}
}
profile
안녕하세요 :)

0개의 댓글