백준 10164번 (C++)

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

10164번: 격자상의 경로

1. 문제

 행의 수가 N이고 열의 수가 M인 격자의 각 칸에 1부터 N×M까지의 번호가 첫 행부터 시작하여 차례로 부여되어 있다. 격자의 어떤 칸은 ○ 표시가 되어 있다. (단, 1번 칸과 N × M번 칸은 ○ 표시가 되어 있지 않다. 또한, ○ 표시가 되어 있는 칸은 최대 한 개이다. 즉, ○ 표시가 된 칸이 없을 수도 있다.) 
 행의 수가 3이고 열의 수가 5인 격자에서 각 칸에 번호가 1부터 차례대로 부여된 예가 아래에 있다. 이 격자에서는 8번 칸에 ○ 표시가 되어 있다.

 격자의 1번 칸에서 출발한 어떤 로봇이 아래의 두 조건을 만족하면서 N×M번 칸으로 가고자 한다. 
 조건 1: 로봇은 한 번에 오른쪽에 인접한 칸 또는 아래에 인접한 칸으로만 이동할 수 있다. (즉, 대각선 방향으로는 이동할 수 없다.)
 조건 2: 격자에 ○로 표시된 칸이 있는 경우엔 로봇은 그 칸을 반드시 지나가야 한다. 
 위에서 보인 것과 같은 격자가 주어질 때, 로봇이 이동할 수 있는 서로 다른 경로의 두 가지 예가 아래에 있다.
 1 → 2 → 3 → 8 → 9 → 10 → 151 → 2 → 3 → 8 → 13 → 14 → 15
 격자에 관한 정보가 주어질 때 로봇이 앞에서 설명한 두 조건을 만족하면서 이동할 수 있는 서로 다른 경로가 총 몇 개나 되는지 찾는 프로그램을 작성하라. 

문제 그림

2. 입력 / 출력

 가. 입력

 입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으로 구분된다. K의 값이 0인 경우도 있는데, 이는 ○로 표시된 칸이 없음을 의미한다. N과 M이 동시에 1인 경우는 없다.

• 행의 수(N), 열의 수(M) (1 ≤ N, M ≤ 15)
• ○로 표시된 칸의 번호(K=0 or 1<K<N×M)

 

 나. 출력

주어진 격자의 정보를 이용하여 설명한 조건을 만족하는 서로 다른 경로의 수를 계산하여 출력해야 한다. 

 

3. 알고리즘

• 고등학교 수학시간에 배운 "같은 것이 있는 순열" 응용 문제 중에 최단경로의 수를 구하는 문제가 있는데, 조건 1, 조건 2 때문에 이 문제도 결국 최단경로의 수를 구하는 문제이다.
• 문제에서 준 그림을 아래의 그림과 같이 변형하면 된다.

  

• 1에서 8까지 가는 최단경로의 수를 구하고, 8에서 15로 가는 최단경로의 수를 구한 다음에 둘을 곱하면 된다.

  

• K=0 인 경우, (N-1)×(M-1)인 표가 있다고 생각하고 (0,0)에서 (N-1,M-1)으로 가는 최단경로의 수를 구하면 된다.
• K≠0 인 경우, (N-1)×(M-1)인 표가 있고 K인 점을 꼭 지나가야 하는 최단경로 수를 구하면 된다. 이때, K를 어떻게 좌표로 표현할 것인가가 문제가 된다.

  1. x좌표   x좌표 = K%N;  if (K>=N || K%N==0) {   x좌표 = N;  } 2. y좌표   y좌표 = K/N;  if (K<M || K%N>0) {   y좌표 = y좌표+1;  }

• K의 좌표를 위와 같은 방법으로 구했으므로 특정한 점을 반드시 지나가는 최단경로의 수를 구하면 된다.

 

4. 전체 코드

#include <stdio.h>

int i, j, N, M, k;
double factorial(double n);

double factorial(double n) {
	double fac = 1;
	for (i = 1; i < n + 1; i++) {
		fac = fac * i;
	}
	return fac;
}

int main() {
	double NOC, NOC1, NOC2;
	int point1, point2;

	scanf_s("%d %d %d", &N, &M, &k);
	while (1) {
		if ((N == 1 && M == 1)||(k == 1)||(k == M * N)) {
			scanf_s("%d %d %d", &N, &M, &k);
		}
		else break;
	}

	if (k == 0) {
		NOC = factorial(N + M - 2) / factorial(N - 1) / factorial(M - 1);
	}
	else {
		point1 = k % N;
		if (k >= N && k % N == 0) {
			point1 = N;
		}
		point2 = k / N;
		if (k < M || k % N >0) {
			point2 += 1;
		}
		NOC1 = factorial(point1 + point2 - 2) / factorial(point1 - 1) / factorial(point2 - 1);
		NOC2 = factorial(N + M - point1 - point2) / factorial(N - point1) / factorial(M - point2);
		NOC = NOC1 * NOC2;
	}

	printf("%.lf\n", NOC);
}

 

5. 코드 세부 설명

 가. 변수 설정, 함수 선언

#include <stdio.h>

int i, j, N, M, k;
double factorial(double n);

• i, j : 반복문을 사용하기 위한 변수
• N : 행의 수 (1 ≤ N, M ≤ 15)
• M : 열의 수 (1 ≤ N, M ≤ 15)
• k : ○가 그려진 숫자

함수가 두 개이기 때문에 전역 변수를 선언해주었다.

• factorial(double n) : 팩토리얼 계산을 위해 선언한 함수

 나. 팩토리얼 함수

double factorial(double n) {
	double fac = 1;
	for (i = 1; i < n + 1; i++) {
		fac = fac * i;
	}
	return fac;
}

• fac : 팩토리얼 계산 결과 값

 팩토리얼을 계산하고 그 값(fac)을 반환한다.

 다. 메인 함수

int main() {
	double NOC, NOC1, NOC2;
	int point1, point2;

• NOC (Number Of Cases) : 경우의 수
• NOC1 : (0,0)에서 K까지의 최단경로의 수
• NOC2 : K에서 (N-1,M-1)까지의 최단경로의 수

계산 과정에서 값이 정수 범위보다 커지기 때문에 int가 아니라 double로 선언했다.

scanf_s("%d %d %d", &N, &M, &k);
while (1) {
	if ((N == 1 && M == 1)||(k == 1)||(k == M * N)) {
		scanf_s("%d %d %d", &N, &M, &k);
	}
	else break;
}

N, M이 둘 다 1이어도 안 되고, K가 1이어도 안 되고, K가 M×N이어도 안 되므로 제대로 된 값이 들어올 때까지 값을 계속 받는다.

if (k == 0) {
	NOC = factorial(N + M - 2) / factorial(N - 1) / factorial(M - 1);
}
else {
	point1 = k % N;
	if (k >= N && k % N == 0) {
		point1 = N;
	}
	point2 = k / N;
	if (k < M || k % N >0) {
		point2 += 1;
	}
	NOC1 = factorial(point1 + point2 - 2) / factorial(point1 - 1) / factorial(point2 - 1);
	NOC2 = factorial(N + M - point1 - point2) / factorial(N - point1) / factorial(M - point2);
	NOC = NOC1 * NOC2;
}

	printf("%.lf\n", NOC);

최단경로의 수 구하는 방법을 풀어놓은 부분이다. 마지막에는 NOC값을 출력하되, 소수점을 출력하지 않는다.