[SDS 알고리즘 특강 복습] 1103 게임 (DFS / 백트래킹 + dp)

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

 

 

DFS로 푸는 문제. 그러나 그냥 dfs로 풀면 시간초과가 뜸. DP를 사용해줘야 문제가 풀림.

 

DFS 아이디어를 떠올리는데 굉장히 낑낑댔지만 결국 떠올리고 코드로 구현해냄!!!!!

그런데 아이디어를 떠올리는 시간이 굉장히 오래걸려, 코드 리뷰를 통해 DFS에 대한 이해를 확실히 하자. 

 

DFS로 한 방에 구현하고 모든 테스트케이스 통과, 엣지케이스 없다고 판단해서 제출함.

그런데 시간초과가 뜸..!!

고려 못한 경우가 2가지였음

 

1. flag처리하고 모든 dfs초반부에 flag값이 1이면 return하는 코드 작성하는 아이디어를 못떠올림

    방문했던 노드면 return만 해버려서 flag가 1이 됐는데(무한사이클이 가능한데) 다른 노드들에 대해서 쓸데 없는 검사를 진행하게 됨.

2. 결국 그래프를 엄청 많이 순회할텐데(시간복잡도를 구할 수 없는 케이스) 이 경우에 dp를 써야함을 인지하지 못하였음. 지났던 노드를 또 지나므로 dp를 사용해서 불필요한 재검사를 하지 않게 코드를 짰어야했는데 이에 대한 고려를 하지 못함

 

dfs flag한 번 업데이트하면 종료조건에 달기, 시간복잡도 구할 수 없는 그래프 순회 문제는 dp사용을 고려하기!

 

그래도 이거 첫날에 특강 들을 때 이거 어떻게 풀지 했었는데

지금와서 백지상태에서 코드짜낸 내가 자랑스럽고 성장한게 느껴져서 성취감 든다!

 

dfs: 종료조건 / 다음노드에 대해 순회 

      이게 끝인 듯? 그리고 모든 탐색경로 하려면 |visted true 탐색 visited false| 요 구조 이해하면 됨.

 

---

아 그리고

이거 입력받는거 애먹었는데

알아야할 팁들 정리해놓으면

 

1. 문자를 숫자로 바꾸려면 '0'을 빼주면 됨

2. String[] s = br.readLine().split("")

    for(int j=0; j<M; j++) {

        arr[i][j] = Integer.parseInt(s[j])

    }
    이렇게 하면 문자로 입력된 숫자가 정수형으로 저장될 수 있음

 

---

<내 정답 코드; visited로 풀다가 dp를 우랴부랴 추가해 2개가 혼재해있음. dp를 쓰면 사실 visited를 쓸 필요가 없을 듯>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static int N, M;
    static int[][] map;
    static boolean[][] visited;
    static int max;
    static int flag = 0;

    // 상하좌우
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    static int[][] dp;

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

        for (int i=0; i<N; i++) {
            String s = br.readLine();
            for(int j=0; j<M; j++) {
                if (s.charAt(j) == 'H') {
                    map[i][j] = -1;
                }
                else {
                    map[i][j] = s.charAt(j) - '0';
                }
            }
        }

        /* 문제 설계
        시작점(0,0)에서 dfs 돌리기. dfs에 현좌표, 동전 던진 횟수 인자로.
        만약 방문했던 노드 다시 방문하면 -1 출력 및 return
        만약 다음 노드가 맵 바깥이면 max값 업데이트
        visited true
        dfs(다음좌표)
        visited false
         */
        dfs(0,0, 1);
        System.out.println(flag == 1 ? -1 : max);

    }

    // (x,y)에서 동전 n번 던진 상태(이번에 던지는 것 포함)의 dfs
    static void dfs(int x, int y, int n) {
        if(flag == 1) return;
        if(visited[x][y] == true) {
            flag = 1;
            return;
        }
        dp[x][y] = n;

        for(int i=0; i<4; i++) {
            int nx = x + map[x][y] * dx[i];
            int ny = y + map[x][y] * dy[i];

            if(nx>=N || ny>=M || nx<0 || ny<0 || map[nx][ny] == -1) {
                max = Math.max(max, n);
            }
            else if(dp[nx][ny] >= n+1) {
                continue;
            }
            else {
                visited[x][y] = true;
                dfs(nx, ny, n + 1);
                visited[x][y] = false;
            }
        }
    }
}