SWEA 2819번: 격자판의 숫자 이어 붙이기 (dfs 이용)

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&problemLevel=4&contestProbId=AV7I5fgqEogDFAXB&categoryId=AV7I5fgqEogDFAXB&categoryType=CODE&problemTitle=&orderBy=RECOMMEND_COUNT&selectCodeLang=ALL&select-1=4&pageSize=10&pageIndex=1

SW Expert Academy

 

[문제]

4×4 크기의 격자판이 있다. 격자판의 각 격자칸에는 0부터 9 사이의 숫자가 적혀 있다.

격자판의 임의의 위치에서 시작해서, 동서남북 네 방향으로 인접한 격자로 총 여섯 번 이동하면서, 각 칸에 적혀있는 숫자를 차례대로 이어 붙이면 7자리의 수가 된다.

이동을 할 때에는 한 번 거쳤던 격자칸을 다시 거쳐도 되며, 0으로 시작하는 0102001과 같은 수를 만들 수도 있다.

단, 격자판을 벗어나는 이동은 가능하지 않다고 가정한다.

격자판이 주어졌을 때, 만들 수 있는 서로 다른 일곱 자리 수들의 개수를 구하는 프로그램을 작성하시오.

[입력]

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스마다 4개의 줄에 걸쳐서, 각 줄마다 4개의 정수로 격자판의 정보가 주어진다.

[출력]

각 테스트 케이스마다 ‘#x ’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 격자판을 이동하며 만들 수 있는 서로 다른 일곱 자리 수들의 개수를 출력한다.
 

[입출력 예시]

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>

int board[4][4];

int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0,-1, 1 };

int numbers[10000000];

void dfs(int x, int y, int depth, int cur_num) {

	if (depth == 7) {
		numbers[cur_num] = 1;
		return;
	}
	

	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];

		//격자 밖으로 벗어난 경우 무시
		if (nx < 0 || nx>3 || ny < 0 || ny>3)
			continue;
		
		dfs(nx, ny, depth + 1, cur_num * 10 + board[nx][ny]);
	}
}

int main() {
	int tc;
	scanf("%d", &tc);
	
	for (int i = 1; i <= tc; i++) {
	
		//격자판 입력 받기
		for (int j = 0; j < 4; j++) {
			for (int k = 0; k < 4; k++) {
				scanf("%d", &board[j][k]);
			}
		}
		
		//numbers 초기화
		for (int j = 0; j < 10000000; j++) {
			if (numbers[j])
				numbers[j] = 0;
		}

		//격자판의 모든 곳에서 입력 시작
		for (int j = 0; j < 4; j++) {
			for (int k = 0; k < 4; k++) {
				dfs(j, k, 1, board[j][k]);
			}
		}

		//numbers[j]==1인 점 찾기
		int cnt = 0;
		for (int j = 0; j < 10000000; j++) {
			if (numbers[j])
				cnt++;
		}
		
		printf("#%d %d\n", i, cnt);
	}

	return 0;
}