백준 숫자판별하기 22101

1. 백준 숫자판별하기 22101번

1.1. 컴퓨팅적 사고

1. 하나의 그래프 클래스를 만들어서 모든 맵의 x,y좌표로 생성한다
2. DFS를 수행하여 모든맵의 x,y좌표를 순회한다.
3. 종료조건은 cnt의 개수가 6개가 만족되면 종료한다.
4. 총 4가지 방향으로 동서남북의 direction 변수로 핸들링을 진행한다.
5. isCheckRange함수에 맞게 이동한 값이 범위에 맞지 않으면 다음값으로 진행한다.
6. DFS 다음 재귀호출은 (다음 X, 다음 Y, 선택된 개수 + 1, 현재값 * 10 + 추가할 값)을 수행한다
7. 종료조건시에 정답을 구하기 위해 하나의 Set 자료구조를 선언하여 현재까지 진행된 값을 add해준다.
8. 문자열로 추가하지 않고 num의 값으로 추가해 나가는 방식은 (현재 값 * 10 + 추가하는 값)으로 구해줄 수 있다. 복잡도면에서 우수할 것으로 생각한다 단순히 O(1)을 가질 것이라고 생각하기 때문이다.

1.2. 시간복잡도

N의 범위는 5이고 모든 맵의 범위는 5*5=25를 가지고 있다. 그리고 총 이동할 수 있는 경우의수는 자기자신의 범위를 제외한 5번이므로 4^5 * 25의 시간복잡도를 가질 수 있다.

1.3. 소스코드

package Samsung.Practice;

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

public class 숫자판점프_2210 {
    static int[][] map;
    static List<Graph> arrList;
    static List<Integer> selectList;
    static int[][] dir = {{0,1},{0,-1},{1,0},{-1,0}};
    static int n;
    static Set<Integer> s = new HashSet<>();
    static boolean[][] isCheck;
    public static void main(String[] args) throws IOException {
        n = 5;
        map = new int[n][n];
        isCheck = new boolean[n][n];
        arrList = new ArrayList<>();
        selectList = new ArrayList<>();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<n; j++){
                map[i][j] = Integer.parseInt(st.nextToken());
                arrList.add(new Graph(i,j));
            }
        }
        for (int i = 0; i < arrList.size(); i++) {
            Graph graph = arrList.get(i);
            dfs(graph.x,graph.y,0, 0);
        }
        System.out.println(s.size());
    }

    private static void dfs(int x, int y,int cnt, int num) {

        if(cnt == 6){
            s.add(num);
            return;
        }
        for(int i=0; i<4; i++) {
            int mx = x + dir[i][0];
            int my = y + dir[i][1];
            if (isCheckRange(mx, my)) continue;
            dfs(mx, my, cnt + 1, num * 10 + map[mx][my]);
        }
    }
    private static boolean isCheckRange(int mx, int my) {
        if(mx < 0 || mx >= n || my < 0 || my >= n){
            return true;
        }
        return false;
    }

    private static class Graph {
        int x;
        int y;

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