소프티어 - 순서대로 방문하기(백트레킹)

처음에는 dfs를 사용하여 stack을 사용해 풀려고 했으나 중복 제거를 처리하지 못해 풀지 못했다.

서로 다른 경우의 수를 구할 때는 백트레킹을 이용해서 풀어보자!

백트레킹은 재귀를 이용해 방문하고 방문 처리한 곳을 다시 취소하는 방법으로 거슬러 올라간다.

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

public class OrderVisit {
	
	static int[] x_move = {1,0,-1,0};
	static int[] y_move = {0,1,0,-1};
	
	//내가 방문한 target의 이전 순서는 다 방문했고, 이후 순서는 아직 방문 안 했는지 판단
	public static boolean isValid(int[][] target, int my_x, int my_y, boolean[][] visited) {
		boolean flag = true;
		loop:
			for(int i=0; i<target.length; i++) {
				if(target[i][0] == my_x && target[i][1] == my_y) {
					//i번째 target 방문한거
					for(int j=0; j<i; j++) {
						//i번째 target 전은 다 방문해야함
						if(!visited[target[j][0]][target[j][1]]) {
							flag = false;
							break loop;
						}
					}
					for(int j=i+1; j<target.length; j++) {
						//i번째 target 이후는 다 안 방문했어야함
						if(visited[target[j][0]][target[j][1]]) {
							flag = false;
							break loop;
						}
					}
				}
			}
		return flag;
	}
	
	public static int findTarget(int[][] graph, int[][] target, int start_x, int start_y, boolean[][] visited) {
		if(target[target.length-1][0] == start_x && target[target.length-1][1] == start_y && isValid(target,start_x, start_y, visited)) {
			//마지막 타겟 지점에 도착
			return 1;
		}
		
		int ans = 0;
		
		//현재 위치를 방문 표시
		visited[start_x][start_y] = true;
	
		//현재 위치에서 상하좌우 이동
		for(int i=0; i<4; i++) {
			int next_x = start_x + x_move[i];
			int next_y = start_y + y_move[i];
			
			if(next_x < 0 || next_x >= graph.length || next_y < 0 || next_y >= graph.length || graph[next_x][next_y] == 1 || visited[next_x][next_y] || !isValid(target,next_x, next_y, visited)) {
				//갈 수 없음
				continue;
			}
			ans += findTarget(graph, target, next_x, next_y, visited);
			
		}
		
		//현재 위치에서 빠져 나올 때 방문 표시 해제(백트레킹)
		visited[start_x][start_y] = false;
		
		return ans;
	}
	
	
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine()); 
		
		
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		int[][] graph = new int[n][n];
		int[][] target = new int[m][2];
		boolean[][] visited = new boolean[graph.length][graph.length];
		
		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());
			for(int j=0; j<2; j++) {
				target[i][j] = Integer.parseInt(st.nextToken())-1;
			}
		}
		int start_x = target[0][0];
		int start_y = target[0][1];  //출발지
		
		
		
		System.out.println(findTarget(graph,target,start_x, start_y, visited));
	}

}