[소프티어] 순서대로 방문하기 자바 풀이 DFS 백트래킹 (HSAT 7회 정기 코딩 인증평가 기출)

[소프티어] 순서대로 방문하기 자바 풀이 DFS 백트래킹 (HSAT 7회 정기 코딩 인증평가 기출)

 

잊을만 하면 찾아오는 소프티어.

이젠 일상인 것 같다.

 

문제보자.

https://softeer.ai/practice/6246

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

 

 

백트래킹(Backtracking) 개념

백트래킹은 문제 해결을 위한 알고리즘적 기법 중 하나로, 모든 가능한 경우의 수를 탐색하여 정답을 찾는 방법입니다. 백트래킹은 재귀적으로 탐색을 진행하면서, 해당 경로가 유효하지 않다면 이전 단계로 돌아가 다른 경로를 시도하는 방식입니다. 쉽게 말해, 탐색 중에 조건을 만족하지 않는 경로가 발견되면 그 즉시 탐색을 중단하고, 다른 가능한 경로를 찾는 전략입니다.

 

 

 

핵심 설명

첫번째 지점을 시작점으로 출발해서

 

방문표시해주고

 

현재위치가

if 방문지점이라면 { cnt+1 넘기기 };

else if 방문지점이 아니라면 { cnt 넘기기 };

방문표시 지워주고

 

 

 

전체 코드

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

public class Main {
    
  public static int dap = 0;
  public static int dx[] = {-1, 0, 1, 0};
  public static int dy[] = {0, 1, 0, -1};
  public static int n = 0;
  public static int m = 0;
  public static int stay[][];
    
  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());
    
    int map[][] = new int[n+1][n+1];
    int v[][] = new int[n+1][n+1];
    stay = new int[m+1][n+1];
    
    for(int i=1; i<n+1; i++){
        st = new StringTokenizer(br.readLine());
        for(int j=1; j<n+1; j++){
            int b = Integer.parseInt(st.nextToken());
            map[i][j] = b;
            v[i][j] = 0;
            // stay[i][j] = 0;
        }
    }
    
    int startX = 0;
    int startY = 0;
    for(int i=0; i<m; i++){
        st = new StringTokenizer(br.readLine());
        int x = Integer.parseInt(st.nextToken());
        int y = Integer.parseInt(st.nextToken());
        stay[i][0] = x;
        stay[i][1] = y;
        
        if(i==0){startX = x; startY = y;}
    }
    
    v[startX][startY] = 1;
    dfs(map, v, startX, startY, 1);
    
    System.out.println(dap);
  }
  
  public static void dfs(int map[][], int v[][], int x, int y, int cnt){
     
      // System.out.println("[" + x + "," + y + "] : " + cnt + " / " + dap);
      
      // 모든 방문지점 도착했다면
      if(m == cnt){
          dap++;
          return;
      }
      
      for(int i=0; i<4; i++){
          int nx = x + dx[i];
          int ny = y + dy[i];
          
          // 밖으로 나가거나, 기방문이거나, 벽이면 continue (백트래킹의 가지치기)
          if( nx < 1 || ny < 1 || nx > n || ny > n || v[nx][ny] == 1 || map[nx][ny] == 1){
              continue;
          }
          
          // 이동
          v[nx][ny] = 1;
          if(stay[cnt][0] == nx && stay[cnt][1] == ny){ // 현재위치가 방문지점이라면
              dfs(map, v, nx, ny, cnt+1);
          }else{ // 현재위치가 방문지점이라면
              dfs(map, v, nx, ny, cnt);
          }
          v[nx][ny] = 0;  // 백트래킹의 이동 후 다시 방문하지 않은 상태를 만들어 가능한 모든 경우의 수를 찾는다
          // System.out.println("[" + nx + "," + ny + "] : go " + dx[i] + "/" + dy[i] + " " + depth);
      }
      
  }
  
}