소프티어 HSAT 기출 Lv3 순서대로 방문하기 java 풀이

 

- 문제 참고

https://softeer.ai/practice/6246/history?questionType=ALGORITHM

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

 

- 풀이

 

간단한 백트래킹이었는데.. 오랜만에 풀기도 하고 자바로 풀다 보니 굉장히 헤맸다.
백트래킹을 통해서 모든 경로를 계산하고 도착지점에 도착할 때마다 방문 순서가 주어진 순서와 일치하는지 검사하는 함수를 통해서 검사하고 카운트를 하나씩 올려준다.
제약조건이 2 <= n <= 4이고 방향은 4방향 방문 순서는 총 n 제곱이었기 때문에 충분히 시간복잡도를 만족하며 계산 가능하다고 판단하여 백트래킹으로 모든 경로를 계산하였다.

 

+

 

문제를 잘못 이해하여 방문순서가 일치하여야 하는데 순서는 일치하지 않고 같은 곳을 방문했다면 카운트를 해주었더니 부분 점수를 받게 되었다. 정확하게 풀려면 방문순서를 List로 저장해두었다가 체크 함수로 검사를 할 때 방문순서까지 고려하여 체크를 해준다면 해결이 가능하다.

 

 

 

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

public class Main {


    static int []dy = {0,0,-1,1};
    static int []dx = {-1,1,0,0};
    static int n;
    static int m;
    static int ans = 0;
    static List<Point> points = new ArrayList<>();
    static int [][] graph  = new int[4][4];


    public static class Point{
        int x;
        int y;

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

    public static Boolean checkRoutes(List<Point> routes){


        int tempIndex = 0;
        int findCount = 0;

        for(int i = 0; i < points.size(); i++){
            for(int j = tempIndex; j < routes.size(); j++){

                if(points.get(i).x == routes.get(j).x && points.get(i).y == routes.get(j).y){
                    tempIndex = j+1;
                    findCount++;
                    break;
                }
                
            }

        }

        if(findCount == points.size()){
            return true;
        }
        return false;

      
    }
    

    public static void dfs(int x, int y, int[][] visited, List<Point> routes){

        // System.out.println((y+1) + " " + (x+1));

        visited[y][x] = 1;
        routes.add(new Point(x,y));


        if(x == points.get(points.size()-1).x && y == points.get(points.size()-1).y){
            // System.out.println("arrived" + " " + (y+1) + " " + (x+1));

            if(checkRoutes(routes)){
                ans++;
            }
            
        }


        for(int i = 0 ; i < 4; i ++){

            int nx = dx[i] + x;
            int ny = dy[i] + y;

            if(nx >= 0 && ny >= 0 && nx < n && ny < n && visited[ny][nx] == 0 && graph[ny][nx] == 0){
                
                dfs(nx,ny,visited,routes);
                visited[ny][nx] = 0;
                routes.remove(routes.size()-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());

        int [][]visited = new int[4][4];
        List<Point> routes = new ArrayList<>();

        

        //그래프 생성
        for(int i = 0 ; i < n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0 ; j < n; j++){
                graph[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        //방문지점 저장
        for(int i = 0 ; i < m; i++){
            st = new StringTokenizer(br.readLine());
            int y = Integer.parseInt(st.nextToken()) - 1;
            int x = Integer.parseInt(st.nextToken()) - 1;
            Point point = new Point(x,y);

            // System.out.println(y + " " + x);
            
            points.add(point);
        }

        dfs(points.get(0).x, points.get(0).y,visited,routes);

        System.out.println(ans);
        
        
        
        



        
    }
}