[백준] 컴백홈
문제 링크 : https://www.acmicpc.net/problem/1189
1189번: 컴백홈
첫 줄에 정수 R(1 ≤ R ≤ 5), C(1 ≤ C ≤ 5), K(1 ≤ K ≤ R×C)가 공백으로 구분되어 주어진다. 두 번째부터 R+1번째 줄까지는 R×C 맵의 정보를 나타내는 '.'과 'T'로 구성된 길이가 C인 문자열이 주어진다
www.acmicpc.net
문제를 처음 봤을 때 거리가 K인 조건을 생각 안하고 풀어서 다른 결과가 나와서 당황했던 기억이 난다.
처음 봤을 때 처음 시작하는 부분에서 집까지 가는 거리를 구하니까 DFS로 구해야 겠다고 생각했다.
이렇게 생각하게 된 계기는 다음과 같다.
DFS는 깊이 탐색으로 한 노드를 시작점으로 잡는다면 깊이로 탐색(?) 한다고 생각하면 된다.
이전에 정리했었던 DFS를 다시 한번 보게 되는 계기가 되었다.
DFS의 탐색 과정은 아래 그림과 같다.
DFS를 사용하는 데에 Stack을 사용하는데, 스택에 값을 넣고 인접한 노드를 검사한 후 제일 위에 있는 값을 꺼내서 인접 노드를 확인하는 방식이다.
여기서 DFS와 다른 하나는 문제에서는 T가 제시되어 있는데, T를 만나면 빗겨가야 한다는 것이다. 즉 T를 만나면 그 이전 노드로 다시 돌아가야 한다.
이 문제에 대한 그림을 그려봤다.
처음 구현했던 코드는 아래와 같다.
package baekjoon;
import java.util.Scanner;
public class ComeBackHome_1189 {
static int R;
static int C;
static int K;
static int arr[][];
static boolean visited[][];
static int answer;
static void solution(int x, int y, int dist) {
// 집 좌표에 도착했다면
if(x==0 && y==C-1) {
if(dist == K) {
answer ++;
}
return ;
}
visited[x][y] = true;
int dx[] = {0, 1, 0, -1};
int dy[] = {-1, 0, 1, 0};
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx < 0 || ny < 0 || nx > R-1 || ny > C-1) {
continue;
}
if(arr[nx][ny] == 1 || visited[nx][ny] == true) {
continue;
}
visited[nx][ny] = true;
solution(nx, ny, dist+1);
visited[nx][ny] = false;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
R = sc.nextInt();
C = sc.nextInt();
K = sc.nextInt();
arr = new int[R][C];
visited = new boolean[R][C];
// 장애물 있는 곳 T -> 1로 표시
for (int i = 0; i < R; i++) {
String tmp = sc.nextLine();
for (int j = 0; j < tmp.length(); j++) {
String str = tmp.substring(j, j+1);
if(str.equals("T")) {
arr[i][j] = 1;
} else {
arr[i][j] = 0;
}
}
}
// 시작 좌표
solution(R-1, 0, 0);
System.out.println(answer);
}
}
코드에 대한 자세한 설명은 아래와 같다.
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
R = sc.nextInt();
C = sc.nextInt();
K = sc.nextInt();
arr = new int[R][C];
visited = new boolean[R][C];
// 장애물 있는 곳 T -> 1로 표시
for (int i = 0; i < R; i++) {
String tmp = sc.nextLine();
for (int j = 0; j < tmp.length(); j++) {
String str = tmp.substring(j, j+1);
if(str.equals("T")) {
arr[i][j] = 1;
} else {
arr[i][j] = 0;
}
}
}
// 시작 좌표
solution(R-1, 0, 0);
System.out.println(answer);
}이 코드는 입력을 받는 부분으로 for문을 돌면서 T가 있다면 1, 그렇지 않다면 0을 값으로 넣었다.
왼쪽 아래에서 DFS를 시작하므로 완쪽 아래의 좌표를 solution 메소드에 넣어줬다.
solution에 대한 코드는 아래와 같다.
static void solution(int x, int y, int dist) {
// 집 좌표에 도착했다면
if(x==0 && y==C-1) {
if(dist == K) {
answer ++;
}
return ;
}
visited[x][y] = true;
int dx[] = {0, 1, 0, -1};
int dy[] = {-1, 0, 1, 0};
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx < 0 || ny < 0 || nx > R-1 || ny > C-1) {
continue;
}
if(arr[nx][ny] == 1 || visited[nx][ny] == true) {
continue;
}
visited[nx][ny] = true;
solution(nx, ny, dist+1);
visited[nx][ny] = false;
}
}if문은 answer 값을 더해주는 조건으로 만약 집 좌표를 만났고, 제시된 거리만큼 움직여 집에 도착하였다면 answer값에 1을 더해주고 재귀를 멈추게 하였다.
arr[2][0] 에서 처음 시작하므로 그림을 그리면 다음과 같다.
그 이전에는 파라메터로 들어온 값에 상하좌우를 탐색하는 dx, dy 배열을 돈다. 만약 배열 인덱스에 벗어나거나 T곧 장애물 값이 있거나 이미 방문했던 곳이라면 continue를 통해 탐색하지 않는다.
여기서 왼쪽과 아래쪽은 인덱스에서 벗어나므로 탐색하지 않고 윗쪽과 오른쪽을 탐색한다.
만약 오른쪽을 탐색한다면 오른쪽 좌표인 visited[1][0]을 true로 바꾸고 여기서 다시 상하좌우를 탐색한다.
조건에 모두 통과과 되었다면 visited 배열에서 true 값으로 해주고, 움직였던 값을 하나 더해주고 재귀로 반복한다. 방문한 값은 다시 false로 하여 다른 경로도 탐색할 수 있도록 해준다.
이렇게 해서 이러한 그림이 그려지는데
집이 발견되었으므로 아래쪽은 탐색하지 않는다. 딱 거리가 6이기에 answer에 1을 더해준다.
(1,2) 좌표도 집에 도달할 수 있긴 하지만 이미 6을 넘었기 때문에 의미가 없어서 굳이 세진 않겠다.
이번에는 오른쪽을 한번 시작해보겠다.
좌표 (2,2)에 와서 두 가지 갈림길이 생겼다.
일단 윗쪽부터 탐색을 시작하겠다.
어디로 가나 6은 만족하므로 2가지 길을 찾을 수 있다.
윗쪽을 했으니 이제 오른쪽으로 탐색을 해보겠다.
이렇게 탐색을 하면 1개의 또 다른 길을 발견할 수 있었다.
여기서 처음에 제출했는데 실패가 났다.
왜 실패가 났을까 고민 하였고, IDE에서 돌려봤을 때 결과가 안나왔다.
생각을 다시 해보니 solution 메소드를 시작한 순간부터 이미 dist 곧 거리를 1만큼 간 것인데 0으로 해준게 문제였던거 같다.
이를 해결해주고 나니 통과가 되었다.
