(1) 문제
- 행의 수가 N이고 열의 수가 M인 격자의 각 칸에 1부터 N×M까지의 번호가 첫 행부터 시작하여 차례로 부여되어 있다. 격자의 어떤 칸은 ○ 표시가 되어 있다. (단, 1번 칸과 N × M번 칸은 ○ 표시가 되어 있지 않다. 또한, ○ 표시가 되어 있는 칸은 최대 한 개이다. 즉, ○ 표시가 된 칸이 없을 수도 있다.)
- 조건 1: 로봇은 한 번에 오른쪽에 인접한 칸 또는 아래에 인접한 칸으로만 이동할 수 있다. (즉, 대각선 방향으로는 이동할 수 없다.)
- 조건 2: 격자에 ○로 표시된 칸이 있는 경우엔 로봇은 그 칸을 반드시 지나가야 한다.
- 위에서 보인 것과 같은 격자가 주어질 때, 로봇이 이동할 수 있는 서로 다른 경로의 두 가지 예가 아래에 있다.
- 1 → 2 → 3 → 8 → 9 → 10 → 15
- 1 → 2 → 3 → 8 → 13 → 14 → 15
- 격자에 관한 정보가 주어질 때 로봇이 앞에서 설명한 두 조건을 만족하면서 이동할 수 있는 서로 다른 경로가 총 몇 개나 되는지 찾는 프로그램을 작성하라.
- 격자의 1번 칸에서 출발한 어떤 로봇이 아래의 두 조건을 만족하면서 N×M번 칸으로 가고자 한다.
- 행의 수가 3이고 열의 수가 5인 격자에서 각 칸에 번호가 1부터 차례대로 부여된 예가 아래에 있다. 이 격자에서는 8번 칸에 ○ 표시가 되어 있다.
(2) 입력
- 입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으로 구분된다. K의 값이 0인 경우도 있는데, 이는 ○로 표시된 칸이 없음을 의미한다. N과 M이 동시에 1인 경우는 없다.
(3) 출력
- 주어진 격자의 정보를 이용하여 설명한 조건을 만족하는 서로 다른 경로의 수를 계산하여 출력해야 한다.
(4) 예제 입력 및 출력
(5) 코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class 전화번호목록{
public static void main(String[] args) throws IOException{
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));
//방식 0,0 에서 K까지의 경우의 수 * K에서의 n,m 까지의 경우의 수를 구하면됩니다..
//N은 행 M은 열
StringTokenizer stk = new StringTokenizer(bufferedReader.readLine());
int N = Integer.parseInt(stk.nextToken());
int M = Integer.parseInt(stk.nextToken());
int K = Integer.parseInt(stk.nextToken());
//1부터 검사하기위해 +1 해준 값으로 초기화합니다.
int[][] visitCount = new int[M + 1][N + 1];
Point startPoint = new Point(1,1);
Point targetPoint;
int targetX;
int targetY;
int midCount = 1;
int answer = 0;
if(K != 0){
targetX = K % M;
targetY = (K / M) + 1;
if(targetX == 0){
targetX = M;
targetY --;
}
targetPoint = new Point(targetX,targetY);
midCount = DP(startPoint, targetPoint, visitCount);
startPoint = targetPoint;
}
targetX = M;
targetY = N;
targetPoint = new Point(targetX,targetY);
visitCount = new int[M + 1][N + 1];
answer = DP(startPoint, targetPoint, visitCount) * midCount;
bufferedWriter.write(String.valueOf(answer));
bufferedWriter.flush();
bufferedWriter.close();
bufferedReader.close();
}
public static int DP(Point startPoint, Point targetPoint, int[][] visitCount){
// 피라미드 형태로 생각해서 구현하였습니다.
Queue<Point> queue = new LinkedList<>();
visitCount[startPoint.x][startPoint.y] = 1;
queue.add(startPoint);
while(!(queue.isEmpty())){
Point point = queue.poll();
if(!(point.x == startPoint.x && point.y == startPoint.y)){
visitCount[point.x][point.y] = visitCount[point.x - 1][point.y] + visitCount[point.x][point.y - 1];
}
// 범위 설정 오른쪽 또는 아래로 이동하기 때문에 모든 수가 0보다 크다.
if(point.x < targetPoint.x){
Point newPoint = new Point(point.x + 1,point.y);
queue.add(newPoint);
} else {
if(point.y < targetPoint.y){
Point newPoint = new Point(startPoint.x,point.y + 1);
queue.add(newPoint);
}
}
}
return visitCount[targetPoint.x][targetPoint.y];
}
public static class Point{
private int x;
private int y;
public int getX(){
return this.x;
}
public void setX(int x){
this.x = x;
}
public int getY(){
return this.y;
}
public void setY(int y){
this.y = y;
}
public Point(int x, int y){
this.x = x;
this.y = y;
}
}
}(6) 실행결과
'BaekJoon Algorithm > Java' 카테고리의 다른 글
| [백준알고리즘 - 9251] LCS(Java) (0) | 2021.08.16 |
|---|---|
| [백준알고리즘 - 5052] 전화번호 목록(Java) (0) | 2021.07.18 |
| [백준알고리즘 - 7785] 회사에 있는 사람(Java) (0) | 2021.07.18 |
| [백준알고리즘 - 9086] 문자열(Java) (0) | 2021.07.18 |
| [백준알고리즘 - 7567] 그릇(Java) (0) | 2021.07.18 |
