성능 요약
메모리: 14964 KB, 시간: 836 ms
분류
조합론, 다이나믹 프로그래밍, 수학
제출 일자
2024년 8월 27일 19:00:38
문제 설명
행의 수가 N이고 열의 수가 M인 격자의 각 칸에 1부터 N×M까지의 번호가 첫 행부터 시작하여 차례로 부여되어 있다. 격자의 어떤 칸은 ○ 표시가 되어 있다. (단, 1번 칸과 N × M번 칸은 ○ 표시가 되어 있지 않다. 또한, ○ 표시가 되어 있는 칸은 최대 한 개이다. 즉, ○ 표시가 된 칸이 없을 수도 있다.)
행의 수가 3이고 열의 수가 5인 격자에서 각 칸에 번호가 1부터 차례대로 부여된 예가 아래에 있다. 이 격자에서는 8번 칸에 ○ 표시가 되어 있다.
격자의 1번 칸에서 출발한 어떤 로봇이 아래의 두 조건을 만족하면서 N×M번 칸으로 가고자 한다.
- 조건 1: 로봇은 한 번에 오른쪽에 인접한 칸 또는 아래에 인접한 칸으로만 이동할 수 있다. (즉, 대각선 방향으로는 이동할 수 없다.)
- 조건 2: 격자에 ○로 표시된 칸이 있는 경우엔 로봇은 그 칸을 반드시 지나가야 한다.
위에서 보인 것과 같은 격자가 주어질 때, 로봇이 이동할 수 있는 서로 다른 경로의 두 가지 예가 아래에 있다.
- 1 → 2 → 3 → 8 → 9 → 10 → 15
- 1 → 2 → 3 → 8 → 13 → 14 → 15
격자에 관한 정보가 주어질 때 로봇이 앞에서 설명한 두 조건을 만족하면서 이동할 수 있는 서로 다른 경로가 총 몇 개나 되는지 찾는 프로그램을 작성하라.
입력
입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으로 구분된다. K의 값이 0인 경우도 있는데, 이는 ○로 표시된 칸이 없음을 의미한다. N과 M이 동시에 1인 경우는 없다.
출력
주어진 격자의 정보를 이용하여 설명한 조건을 만족하는 서로 다른 경로의 수를 계산하여 출력해야 한다.
풀이 (DFS)
특이하게도 DP 문제지만, DFS로 접근해 풀었다...
DP 풀이가 궁금해서 따로 구글링을 통해 여러 블로그들을 찾아봤고,
[DP 풀이] 위 풀이를 찾아냈다.
DFS로는 K 값이 0인 경우, 0이 아닌 경우로 나눠 DFS를 실행해 해결했다.
K 값이 0인 경우
- 위 경우는 그냥
1,1을 기준으로N,M까지 DFS를 실행해주고N,M에 도달한 경우에 + 1을 하며 늘려줬다.
K 값이 0이 아닌 경우
위 경우가 이제 문제가 될 수 있는데, 처음엔 따로 boolean 변수를 만들어서 DFS 함수가 해당 K 좌표를 무조건 지나는 경우만 체크할까 고민했었다.
하지만 이 멍청한 어린 양은 백준 질문란에서 힌트를 얻었고,
(1,1)부터 (K의 X좌표, K의 Y좌표)까지 DFS를 진행하는 것 하나.
(K의 X좌표, K의 Y좌표)부터 (N,M)까지 DFS를 진행하는 것 하나.
총 두 갈래로 나눠 DFS를 실행하면 된다는 것을 깨달았다.
사실 이 내용은 고등학교 수학 1학년?때 확률과 통계에서 배웠다.
다만 내 뇌는 그걸 기억할 정도로 똑똑하지 않아서 문제가 됐던 것 뿐 ㅎㅎ;;
정보) 이 내용은 진짜 수학임.
이와 관련된 문제를 푸는 [최단 거리 문제 풀이]를 가져왔다.
아무튼 그래서 즉,
((1,1)부터 (K의 X좌표, K의 Y좌표)까지 DFS) * ((K의 X좌표, K의 Y좌표)부터 (N,M)까지 DFS) 를 계산해준다면, 답을 구할 수 있다는 것이다!
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
//dfs로 해결한 문제
static int N,M,K;
static int[][] map;
static int[] dx = {1,0}; //오른쪽 , 아래
static int[] dy = {0,1};
static boolean[][] visited; //방문 여부 확인용
static int ans=0; //경로 구하기 답
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());
map= new int[N+1][M+1];
visited = new boolean[N+1][M+1];
int X=0; int Y=0;
int distance =0; //배열 번호 매기기
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
distance++;
map[i][j] = distance;
if (distance == K) {
X = i;
Y = j;
}
}
}
if(K==0) { //반드시 지나야하는 구간 없다면 그냥 DFS
dfs(1,1,N,M);
System.out.println(ans);
}
else { //반드시 지나야하는 구간을 기준으로 나누기.
dfs(1,1,X,Y);
int first_ans = ans; //처음 1,1부터 k좌표까지 DFS
ans=0;
dfs(X,Y,N,M);
int second_ans =ans; //k좌표부터 N,M까지 DFS
System.out.println(first_ans * second_ans); //두 값 곱하면 답
}
}
public static void dfs(int x,int y, int end_x, int end_y) {
visited[x][y]=true;
if(x==end_x && y==end_y) {
ans++;
return;
}
for(int i=0; i<2; i++) {
int nx = x+dx[i];
int ny = y+dy[i];
if(nx> N || nx<=0 || ny>M || ny<=0) {
continue;
}
if(visited[nx][ny]) {
continue;
}
visited[nx][ny]=true;
dfs(nx,ny,end_x,end_y);
visited[nx][ny]=false;
}
}
}
