[백준] 1189 컴백홈 - 백트래킹(Backtracking) + DFS(깊이우선탐색) JAVA

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

1189번: 컴백홈

코드설명

백트래킹(Backtracking) + DFS(깊이우선탐색) 을 활용하는 문제입니다.

 

코드의 주요 로직은 다음과 같습니다:

1. DFS 메서드는 현재 위치 (r, c)에서 시작하여 깊이 우선 탐색을 수행합니다.
2. 목적지에 도달하면서 지정된 조건(K번 이동)을 만족하면 answer를 증가시킵니다.
3. 상하좌우로 이동하면서 범위를 벗어나는 위치확인과 방문한 적이 없는지 확인한 후, 재귀적으로 DFS를 호출합니다.

즉,  백트래킹 및 완전탐색을 통해 한수가 집에 갈 수 있는 모든 경로를 구합니다.

해당 경로에서 만약 K번째의 길이라면, 해당 가지수를 세어줍니다.

코드

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

public class Main {
	public static int N, M, R, C, K;
	public static char[][] map;
	public static boolean[][] visited;
	public static int answer = 0;
	public static int[] dx = {-1,1,0,0};
	public static int[] dy = {0,0,-1,1};
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());

    	R = Integer.parseInt(st.nextToken());
    	C = Integer.parseInt(st.nextToken());
    	K = Integer.parseInt(st.nextToken());
    	
    	map = new char[R][C];
    	visited = new boolean[R][C];
    	for(int i=0; i<R; i++) {
    		st = new StringTokenizer(br.readLine());
    		map[i] = st.nextToken().toCharArray();
    	}
    	
    	visited[R-1][0] = true;
    	DFS(0, R - 1, 0);
    	System.out.println(answer);
    }
    
    public static void DFS(int level, int r, int c) {
    	if(r == 0 && c == C-1) {
    		if(level + 1 == K){
    			answer += 1;
    		}
    		return ;
    	}
    	if(level >= R * C) return ;
    	
    	for(int dir = 0; dir < 4; dir++) {
    		int nr = r + dx[dir];
    		int nc = c + dy[dir];
    		if(nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
    		if(map[nr][nc] =='T') continue;
    		
    		if(visited[nr][nc] == false) {
    			visited[nr][nc] = true;
            	DFS(level + 1, nr, nc);
            	visited[nr][nc] = false;	
    		}
    	}
    }
}

 

 

정답코드 2입니다.

더 깔끔한 코드입니다.

문제에서 실수했었던 점은, 맨 첫 시작점의 위치를 방문처리해야합니다.

해당 부분을 놓쳐서 디버깅하는데 시간이 걸렸습니다.

visited[N-1][0] = true;
answer = DFS(1, N-1, 0);

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P, K, A, B, X, L, R;
	static int answer = 0;
	static char[][] arr = new char[5][5];
	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());
		K = Integer.parseInt(st.nextToken());
		arr = new char[N][M];
		visited = new boolean[N][M];
		for(int i=0;i<N; i++) {
			st = new StringTokenizer(br.readLine());	
			arr[i] = st.nextToken().toCharArray();
		}
		visited[N-1][0] = true;
		answer = DFS(1, N-1, 0);
		System.out.println(answer);
	}
	
	static boolean[][] visited = new boolean[5][5];
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0, 0, -1, 1};
	static int DFS(int depth, int r, int c) {
		if(r == 0 && c == M-1 && depth == K) return 1;
		if(depth >= K) return 0;
		
		int ret = 0;
		for(int dir = 0; dir < 4; dir++) {
			int nr = r + dx[dir];
			int nc = c + dy[dir];
			if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
			if(visited[nr][nc] == false && arr[nr][nc] != 'T') {
				visited[nr][nc] = true;
				ret += DFS(depth + 1, nr, nc);
				visited[nr][nc] = false;
			}
		}
		return ret;
	}
	
}