백준 1189번 - 컴백홈

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

1189번: 컴백홈

 

 

 

 

 

어느 한지점에서 시작해서 다른 지점까지 갈 수 있는 모든 방법을 탐색해야 하는 문제이다. 그래프 탐색 + 백트래킹 유형의 문제이다. 백트래킹 문제에서는 재귀를 통한 DFS 탐색으로 푸는 것이 적합하다.

 

그래서 풀면서 같은 유형인 1987번 알파벳과 비슷하다고 생각했다.

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

1987번: 알파벳

 

 

 

 

 

 

풀이

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

public class Main {
	static int R, C, K;
	static int[][] graph;
	static boolean[][] visited;
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	static int answer;

	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());
		
		graph = new int[R][C];
		
		for(int i = 0; i < R; i++) {
			String input = br.readLine();
			
			for(int j = 0; j < C; j++) {
				graph[i][j] = input.charAt(j);
			}
		}
		
		//구현
		visited = new boolean[R][C];
		answer = 0;
		
		dfs(R - 1, 0, 1);
		
		//출력
		System.out.println(answer);
	}

	public static void dfs(int x, int y, int count) {
		if(x == 0 && y == C - 1) { //집까지 도착
			if(count == K) { //거리가 K인 경우
				answer++;
			}
			
			return;
		}
		
		visited[x][y] = true;
		
		for(int i = 0; i < 4; i++) { //상하좌우 탐색
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if(0 <= nx && nx < R && 0 <= ny && ny < C) { //좌표 범위 안에 있고
				if(!visited[nx][ny] && graph[nx][ny] == '.') { //지금까지 방문한 적 없고, 갈 수 있으면
					dfs(nx, ny, count + 1);
				}
			}
		}
		
		visited[x][y] = false; //백트래킹을 위한 방문 체크 해제
	}

}

DFS + 백트래킹이라 시간이 많이 걸릴까봐 걱정했었는데, 문제에서 주어진 입력의 크기가 R(1 ≤ R ≤ 5), C(1 ≤ C ≤ 5), K(1 ≤ K ≤ R×C)로 크지 않아서 시간이 많이 나오진 않았다.

 

 

 

 

 

결과