[자바] 백준 1103 - 게임 (java)

목차

문제 : boj1103

 

 

필요 알고리즘

• 깊이 우선 탐색, DP, 사이클 판정
  
  • memoization을 통해 연산 횟수를 줄이면서 DFS를 진행하는 문제이다. 또한 사이클 판정하는 방법도 알아야 한다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  사실 로직을 말로 하면 간단하다.

1. 가장 왼쪽 위부터 DFS를 진행한다.

2. 사이클이 한번이라도 생기는 경우 -1을 출력하고 끝낸다.

3. 사이클 없이 가장 멀리 간 거리를 출력한다.

 

  일단 위 로직이 시작인데 거기서 좀 더 디테일하게 들어가는 문제이다.

 

  디테일한 부분으로는 우선 사이클 판정은 어떻게 할 수 있을까? 방문체크를 하다가 이미 왔던 곳을 한번 더 갔다면 사이클이 생긴거다.

 

  우선 위 까지 풀었다면 거의 다 푼거다! 다만 시간 초과가 뜰 것이다. 이 부분을 처리하기 위해 memoization을 사용해보자. memoization[x]를 '가장 왼쪽 위부터 시작해 x라는 위치에 도착했을 때, 그 이하로 가장 멀리 도달한 거리' 로 정의했다. 그리고 dfs로 진행하므로, 한번 확정된 memoization 값은 이후에 바뀌는 경우가 없다. 따라서 이미 값이 있다면 그 값을 리턴해주면 된다.

 

  2차원 배열 형태인데 왜 1차원 배열로 처리했냐면, (r, c) 위치를 r*M+c 로 하나의 숫자로 변경해뒀기 때문이다. 사실 굳이 이렇게 할 필요는 없고, 그냥 입력받은 그대로 진행해도 된다. 내 경우 처음에 단방향인걸 잊고 별 생각없이 서로소 집합으로 사이클 판정을 하려고 배열을 그래프 형태로 변경해서 생각했다. 근데 단방향이라 그걸론 사이클 판정이 안되니 방문체크로 판정하는걸로 변경하면서 기존 코드를 그대로 둬서 그렇다.

 

  아무튼 그래서 이하 코드의 로직을 전체적으로 보면

1. 입력받는다.

2. (r, c) 위치를 r*M+c 로 변경한걸 기준으로 그래프로 바꾼다. 그리고 미리 간선을 파악해둔다.

3. dfs를 진행한다.

3.1 이미 memoization 값이 있다면 그걸 리턴한다.

3.2 모든 간선에 대해 dfs를 더 진행한다. 이 때 이미 방문한 곳을 다시 방문한다면 사이클이 생긴 경우이다.

3.3 그리고 모든 간선으로 진행한 경우 중 가장 memoization 값이 큰 경우가 '가장 왼쪽 위부터 시작해 x라는 위치에 도착했을 때, 그 이하로 가장 멀리 도달한 거리' 에 해당하므로, 그 값에 자기 자신을 +1한 값을 memoization에 넣어준다.

 

private int dfs(int idx) {
    if (memoization[idx] != 0) return memoization[idx]; // 3.1

    int max = 0;
    for (int next : edges[idx]) { 

        if (isCycle || v[next]) { // 3.2 (사이클 생긴 경우)
            isCycle = true;
            return -1;
        }

        v[next] = true;

        max = Math.max(max, dfs(next));	// 3.2

        v[next] = false;
    }

    return memoization[idx] = isCycle?-1:1+max; // 3.3
}

  

 

코드 : github

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

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);
    static final int[] DR = {-1,0,0,1};
    static final int[] DC = {0,-1,1,0};
    int r, c;
    List<Integer>[] edges;
    boolean isCycle = false;
    boolean[] v;
    int[] memoization;

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    private void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

        int[][] map = new int[r][c];
        for (int i = 0; i < r; i++) {
            String row = br.readLine();
            for (int j = 0; j < c; j++) {
                char cur = row.charAt(j);
                map[i][j] = cur=='H'?-1:cur-'0';
            }
        }

        edges = new List[r*c];
        for (int i = 0; i < r*c; i++) edges[i] = new ArrayList<>();

        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (map[i][j] == -1) continue;

                int curIdx = i*c+j;
                for (int d = 0; d < 4; d++) {
                    int nr = i+map[i][j]*DR[d];
                    int nc = j+map[i][j]*DC[d];

                    if (nr<0||nr>=r||nc<0||nc>=c||map[nr][nc]==-1) continue;

                    int nextIdx = nr*c+nc;
                    edges[curIdx].add(nextIdx);
                }
            }
        }

        map = null;

        v = new boolean[r*c];
        memoization = new int[r*c];
        v[0] = true;

        System.out.println(dfs(0));
    }

    private int dfs(int idx) {
        if (memoization[idx] != 0) return memoization[idx];

        int max = 0;
        for (int next : edges[idx]) {

            if (isCycle || v[next]) {
                isCycle = true;
                return -1;
            }

            v[next] = true;

            max = Math.max(max, dfs(next));

            v[next] = false;
        }

        return memoization[idx] = isCycle?-1:1+max;
    }
}