[BOJ] 백준 1103번 게임 (Java)

#1103 게임

난이도 : 골드 2

유형 : 그래프 탐색

1103번: 게임

▸ 문제

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

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

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

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

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

 

▸ 입력

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

 

▸ 출력

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

 

 

 

문제 풀이 🖋  

동전이 구멍과 보드밖으로 나가지 않고 최대한 움직일 수 있는 경로를 구하면 된다. 

 

📚 조건

   ∙ 보드 세로 크기 N, 가로크기 M ( 1 <= N,M <= 50)

   ∙ 동전은 가장 왼쪽 위칸에서 시작

   ∙ 동전은 위, 아래, 왼쪽, 오른쪽 4가지 방향으로 이동 가능

   ∙ 동전이 위에서 고른 방향 X만큼 움직임. 이동 중 H는 무시

 

 

처음에 dfs 깊이 탐색으로만 했다가 시간초과가 발생했다. 그래서 메모제이션 dp를 사용해줘야한다. 

 

1) dfs탐색은 스택 재귀호출 방식이기 때문에 한 경로를 다음과 같이 탐색시킬 수 있다. 그래서 해당 경로가 맞지 않을 경우 다시 돌아가서 다른 경로를 탐색시킬 수 있다.

ex) 1 > 3 > 4 (x) 

      1 > 3 > 5 > 2 > 6 (o)

visited[nx][ny]= true;
dfs(nx, ny, cnt+1);	
visited[nx][ny]= false;

 

2) 중요한 부분은 해당 문제는 최대 경로를 구하는 것이기 때문에 cnt를 했는데 탐색한 부분의 cnt(dp[nx][ny])가 더 크다면 탐색을 멈추는 것이다.

if(dp[nx][ny] > cnt) continue;

 

3) 그리고 한 경로 안에서 이미 방문한 곳을 다시 한 번 방문하면 무한루프로 간주하고 리턴시키면 된다.

if(visited[nx][ny]) {
	flag = true;
	return;
}

 

 

풀이 코드 ✔︎ 

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

public class Main {

	static int n,m;
	static int hole = -99;
	static int max=-1;
	static boolean flag= false;
	static int[][] map,dp;
	static boolean[][] visited;
	static int[] dx = {1,-1,0,0};
	static int[] dy = {0,0, 1,-1};
	
	public static void main(String[] args) throws IOException{
		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 int[n][m];
		dp =  new int[n][m];
		visited = new boolean[n][m];
		
		for(int i=0; i<n; i++) {
			String[] line = br.readLine().split("");
			for(int j=0; j<line.length; j++) {
				if(line[j].equals("H")) {
					map[i][j] = hole;
				}else {
					int num = Integer.parseInt(line[j]);
					map[i][j] = num;
				}
			}
		}

		visited[0][0] = true;
		dfs(0,0,1);
		
		if(flag) {
			System.out.println(-1);
		}else {
			System.out.println(max);
		}
	}
	
	static void dfs(int x, int y, int cnt) {
		if(cnt>max) {
			max = cnt;
		}
		dp[x][y] = cnt;
		
		for(int i=0; i<4; i++) {
			int move = map[x][y];
			int nx = x+ (move*dx[i]);
			int ny = y+ (move*dy[i]);
			
			if(nx<0 || ny<0 || nx>n-1 || ny>m-1 || map[nx][ny] == hole) {
				continue;
			}
			
			// 이미 방문한 곳을 다시 한번 방문하면 무한루프로 리턴 
			if(visited[nx][ny]) {
				flag = true;
				return;
			}
			
			// 이미 깊이 탐색한 부분 스킵
			if(dp[nx][ny] > cnt) continue;
			
			visited[nx][ny]= true;
			dfs(nx, ny, cnt+1);	
			visited[nx][ny]= false;
		}
		
	}
}

 

 

+

메모제이션 유무 비교 예시)

맵 크기 : 4X4
3HH2
H1HH
H2H1
2219

 

dp를 적용하지 않았을 때 : 12회

 

dp를 적용했을 때 : 9회

if(dp[nx][ny] > cnt) continue;

 

☛ map크기가 작아 별 차이는 안나지만 이렇게 작은 크기에도 연산횟수가 차이나는 것을 볼 수 있다.