숫자판 점프 / 백준 (Baekjoon) / 2210

---

숫자판 점프 / 백준 (Baekjoon) / 2210

** 여기서 다루는 알고리즘 문제는 저의 창작 문제가 아닐 경우, 저작권 관련 문제를 방지하고자, 문제의 대략적인 설명 및 요구사항만 소개하고 있습니다. 

** 이 공간에서 공유되는 풀이 및 Source code는 제 개인의 학습 목적이며, 당연히 최선의 정답이 아닙니다. 

** 혹시 더 나은 방법이나 아이디어가 있으신 경우에는, 댓글에 의견을 공유해주시면 감사하겠습니다.

** Source code는 C 언어로 작성되었습니다.

---

알고리즘 분류 및 개요

     - Backtracking (백트래킹)

 

 

Input / output

• 입력
  
  다섯 개의 줄에 다섯 개의 정수로 숫자판이 주어진다.
  
  
• 출력
  
  첫째 줄에 만들 수 있는 수들의 개수를 출력한다.

 

주의 사항

• case가 5 * 5 (buffer 크기) * 4 * 4 * 4 * 4 * 4 * 4 (네 방향으로 6 depth) = 102,400 개 밖에 되지 않으므로, 전형적인 backtracking 풀이법으로 풀이가 가능한 문제입니다.
  
  
• 한 번 방문한 node를 재 방문할 수 있음에 주의하여야 하고, VISIT buffer를 활용할 경우, 한 번 나왔던 케이스에 표시를 해서 가능한 case들을 counting하기 때문에, 모든 케이스를 최종적으로 다시 세어보지 않아도 되어, 시간을 단축할 수 있습니다.
  
  
• 문자열이라는 부분에 너무 어렵게 생각할 필요가 없으며, 매 depth마다 MUL_VAL buffer를 활용하여, 값을 누적으로 더해주었더니 max depth에서의 값이 쉽게 도출되었습니다. 이렇게 처리하게 되면 VISIT buffer에 표시하는 것도 용이해 집니다.

Source code

---

///////////////////////////////////////////////
// - Backjoon 2210 : 숫자판 점프
// - https://www.acmicpc.net/problem/2210
///////////////////////////////////////////////

#include <stdio.h>

typedef unsigned int	(u32);
typedef unsigned short  (u16);
typedef unsigned char	(u8);

typedef signed int		(s32);
typedef signed short	(s16);
typedef signed char		(s8);

#define MAX_ARR_SIZE	(5)
#define MAX_DEPTH		(6)

u8 TEST_INPUT[MAX_ARR_SIZE*MAX_ARR_SIZE];
u8 VISIT[999999];
u32 MULT_VAL[6]	= {100000, 10000, 1000, 100, 10, 1};

u32 g_total_case;

typedef struct _tag_POS {
	u8 pos_x;
	u8 pos_y;
}__POS;

static u8 __inline IsComplete( u8 depth )
{
	if (depth == (MAX_DEPTH - 1))	return 1;
	else							return 0;
}

static void FinalProcess( u32 acc_val )
{
	if (VISIT[acc_val] == 0)
	{
		g_total_case++;
		VISIT[acc_val] = 1;
	}
}

static void FindNextTargets( u8 pos_y, u8 pos_x, __POS *next_targets, u8 *num_of_next_targets)
{
	u8 total_next_target_num = 0;

	if (pos_y > 0)
	{
		next_targets[total_next_target_num].pos_x	= pos_x;
		next_targets[total_next_target_num++].pos_y = pos_y - 1;
	}

	if (pos_x > 0)
	{
		next_targets[total_next_target_num].pos_x	= pos_x - 1;
		next_targets[total_next_target_num++].pos_y = pos_y;
	}

	if (pos_x < (MAX_ARR_SIZE - 1))
	{
		next_targets[total_next_target_num].pos_x	= pos_x + 1;
		next_targets[total_next_target_num++].pos_y = pos_y;
	}

	if (pos_y < (MAX_ARR_SIZE - 1))
	{
		next_targets[total_next_target_num].pos_x	= pos_x;
		next_targets[total_next_target_num++].pos_y = pos_y + 1;
	}

	*num_of_next_targets = total_next_target_num;
}

u8 Backtracking( u8 pos_y, u8 pos_x, u8 depth, u32 acc_val )
{
	int i;

	// Check whether this combination is the solution or not.
	if (IsComplete( depth ))
	{
		FinalProcess( acc_val );
	}
	else
	{
		u8 num_of_next_targets = 0;
		__POS next_targets[4];

		// Increase the count of depth.
		depth++;

		// Update the list of next targets and the number.
		FindNextTargets( pos_y, pos_x, next_targets, &num_of_next_targets);

		// Check every feasible target.
		for (i = 0; i < num_of_next_targets; i++)
		{
			u8 next_pos_x = next_targets[i].pos_x;
			u8 next_pos_y = next_targets[i].pos_y;

			u32 next_val = TEST_INPUT[next_pos_y * MAX_ARR_SIZE + next_pos_x];

			acc_val = acc_val + (next_val * MULT_VAL[depth]);
			Backtracking(next_pos_y, next_pos_x, depth, acc_val);
			acc_val = acc_val - (next_val * MULT_VAL[depth]);
		}
	}
}

int main(void)
{
	int i, j;
	u8 temp_char;

	for (i = 0; i < 5; i++)
	{
		for (j = 0; j < 5; j++)
		{
			scanf(" %c", &temp_char);
			TEST_INPUT[i * 5 + j] = temp_char - 48;
		}
	}

	{
		u32 acc_value = 0;

		for (i = 0; i < 5; i++)
		{
			for (j = 0; j < 5; j++)
			{
				acc_value = TEST_INPUT[i * 5 + j] * MULT_VAL[0];
				Backtracking(i, j, 0, acc_value);
			}
		}
	}

	printf("%d", g_total_case);

	return 0;
}

---

난이도 / 중요도 / 재시도

  ★★☆☆☆ / ★★☆☆☆ / x 0

출처 / 관련 링크

- Baekjoon online judge : https://www.acmicpc.net/problem/2210

- Backtracking 알고리즘 소개 : http://jayce-with.tistory.com/16

Test input file

-