[JAVA]백준 1103번: 게임

https://www.acmicpc.net/problem/1103

1103번: 게임

1. 문제 설명

 

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

 

가장 왼쪽 위에서 부터 시작하여 동전이 있는 곳에 쓰여 있는 숫자 X 만큼 위, 아래, 왼쪽, 오른쪽으로 이동한다. 이때 중간에 있는 구멍은 무시하며, 동전이 구멍에 빠지거나, 보드의 바깥으로 나간다면 게임은 종료된다.

 

최대 몇 번 동전을 움직일 수 있는지 구하는 문제이다.

 

2. 풀이

 

bfs + dp / dfs+ dp로 풀 수 있는 문제이다.

 

1) bfs + dp

 

현재 위치에서 위, 아래, 왼쪽, 오른쪽 들 중에서 움직일 수 있는 위치들을 queue에 넣고 queue에 값이 없을 때까지 반복한다. 일반적인 bfs와 같은 형식으로 짜면 된다.

 

다만, 형택이가 무한히 동전을 움직일 수 있는 경우를 고려해야 하는데 이는 MAX값을 정하고 MAX 값 이상으로 형택이가 움직이게 된다면 무한히 동전을 움직일 수 있는 경우라고 판단한다.

MAX값은 N*M의 최대 크기 2500보다 1큰 2501로 설정하였다.

 

dp는 현재 depth에서 중복으로 같은 x,y가 queue에 삽입되는 것을 막기 위해 사용한다.

dp의 값이 현재 depth보다 작은 경우 다시 queue에 삽입되어야 하는데, 왜냐하면 최대 동전의 움직이는 횟수를 구하기 때문에 dp 값보다 depth가 크다면 다시 계산해 봐야 한다. (큰 값을 구하는게 목적이니까!)

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

public class Main {

    public static int N, M;
    public static char[][] map;
    public static boolean[][] visited;
    public static int MAX = 2501;
    public static int[][] dp;
    public static int[][] move = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        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];
        dp = new int[N][M];

        for (int x = 0; x < N; x++) {

            String line = br.readLine();

            map[x] = line.toCharArray();
        }

        int ans = bfs();

        if (ans == MAX) {
            System.out.println("-1");
        } else {
            System.out.println(ans);
        }



    }

    public static int bfs() {
        Queue<Point> queue = new LinkedList<>();

        queue.add(new Point(0, 0));

        int ret = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();

            ret++;

            for (int x = 0; x < size; x++) {

                Point now = queue.poll();

                for (int y = 0; y < 4; y++) {
                    int next_x = now.x + (map[now.x][now.y] - '0') * move[y][0];
                    int next_y = now.y + (map[now.x][now.y] - '0') * move[y][1];

                    if (isValid(next_x, next_y) && dp[next_x][next_y] < ret) {
                        dp[next_x][next_y] = ret;
                        queue.add(new Point(next_x,next_y));
                    }
                }
            }


            if (ret == MAX) {
                break;
            }
        }

        return ret;


    }

    public static boolean isValid(int x, int y) {
        if(x<0 || x>= N || y<0 || y>= M)
            return false;

        if(map[x][y]=='H')
            return false;

        return true;
    }

    public static class Point{
        int x, y;

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

}

 

2) dfs + dp

 

bfs와 유사하게 일반적인 dfs의 방식으로 구현하면 된다.

다만 bfs와 다르게, dp의 값이 있다면 더 dfs 할 필요 없이 dp의 값을 반환하면 된다.

(dp [x][y]의 값이 있다는 것은, 이미 x, y에서 끝까지 depth를 계산했다는 것이기에 다시 계산할 필요가 없다.)

 

dfs의 경우 visited 배열을 사용하여 지나가는 위치들을 기억하고, 이미 지나온 위치를 재방문하게 된다면 무한히 움직이는 것으로 판단한다.

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

public class Main {

    public static int N, M;
    public static int[][] map;
    public static boolean[][] visited;
    public static int MAX = 2501;
    public static int[][] dp;
    public static int[][] move = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N][M];
        visited = new boolean[N][M];
        dp = new int[N][M];

        for (int x = 0; x < N; x++) {

            String line = br.readLine();

            for (int y = 0; y < M; y++) {
                map[x][y] = line.charAt(y) - '0';
            }

        }

        int ans = dfs(0,0);

        if (ans >= MAX) {
            System.out.println("-1");
        } else {
            System.out.println(ans);
        }



    }

    public static int dfs(int x, int y) {

        if(dp[x][y]!=0)
            return dp[x][y];

        int ret = 1;

        for (int idx = 0; idx < 4; idx++) {
            int next_x = x + map[x][y] * move[idx][0];
            int next_y = y + map[x][y] * move[idx][1];

            if (isValid(next_x, next_y)) {
                if(visited[next_x][next_y])
                    return MAX;

                visited[next_x][next_y] = true;
                ret = Math.max(ret, dfs(next_x, next_y) + 1);
                visited[next_x][next_y] = false;

                if(ret>=MAX)
                    return MAX;

            }
        }

        dp[x][y] = ret;
        return ret;




    }

    public static boolean isValid(int x, int y) {
        if(x<0 || x>= N || y<0 || y>= M)
            return false;

        if(map[x][y]=='H'-'0')
            return false;

        return true;
    }



}

dfs

bfs