mingssssss

1. 문제

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

숫자판 점프 성공

문제

5×5 크기의 숫자판이 있다. 각각의 칸에는 숫자(digit, 0부터 9까지)가 적혀 있다. 이 숫자판의 임의의 위치에서 시작해서, 인접해 있는 네 방향으로 다섯 번 이동하면서, 각 칸에 적혀있는 숫자를 차례로 붙이면 6자리의 수가 된다. 이동을 할 때에는 한 번 거쳤던 칸을 다시 거쳐도 되며, 0으로 시작하는 000123과 같은 수로 만들 수 있다.

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

입력
다섯 개의 줄에 다섯 개의 정수로 숫자판이 주어진다.

출력
첫째 줄에 만들 수 있는 수들의 개수를 출력한다.

예제 입력 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 2 1
1 1 1 1 1

예제 출력 1
15

힌트
111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다.

2. 코드

package mymain;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class BOJ_2210 {

	static ArrayList<ArrayList<String>> list;
	static ArrayList<String> answer;
	static Set<String> set; 
	static int[] dx = { -1, 1, 0, 0 };
	static int[] dy = { 0, 0, -1, 1 };
	static String temp;
	static int depth;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		list = new ArrayList<>(); 	 // 입력 받을 ArrayList
//		answer = new ArrayList<>();	 // 답을 출력할 ArrayList
		set = new HashSet<>();		 // 값을 저장할 set

		for (int i = 0; i < 5; i++) {
			list.add(new ArrayList<>());
		}

		for (int i = 0; i < 5; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 5; j++) {
				list.get(i).add(st.nextToken());
			}

		}
		// 입력 종료

		for (int i = 0; i < 5; i++) {
			for (int j = 0; j < 5; j++) {
				temp = "";	// dfs 진입 전 temp값 초기화
				dfs(i, j, list.get(i).get(j));	
			}
		}
		
		// answer에 들어간 값 확인
//		for (int i = 0; i < answer.size(); i++) {
//			System.out.printf("%s ", answer.get(i));
//		}
		System.out.println(set.size());
	}

	private static void dfs(int r, int c, String temp) {

		if (temp.length() == 6) {	// 만들어진 문자열의 길이가 6일 때
//			if (!answer.contains(temp)) {	// 만들어진 문자열과 동일한 답이 answer 리스트에 없다면(중복 피하기 위함)
//				answer.add(temp);	
//			}
			set.add(temp);	// 아예 중복이 허용되지 않는 set 사용
			return;	// 길이가 6이면서 중복인 경우는 return
		}

		for (int i = 0; i < 4; i++) {

			int nextX = r + dx[i];
			int nextY = c + dy[i];

			if (nextX < 0 || nextY < 0 || nextX >= 5 || nextY >= 5) {
				continue;
			}

			dfs(nextX, nextY, temp + list.get(nextX).get(nextY));	// temp에 현재 좌푯값에 있는 숫자를 더해줌
		}

	}
}

3. 리뷰

브루트포스 알고리즘에 dfs를 접목한 문제이다.

중복되지 않는 가능한 한 모든 수를 찾아서 그 개수를 return 하는 문제이다.

dfs 공부 중이고, 정답률이 70%가 넘어서 쉽게 풀 수 있을 줄 알았으나..

저번에 프로그래머스에서 도전하고 실패한 완탐 dfs문제라

접근은 쉬웠지만, 구현이 너무나 어려웠다.

한 2시간 정도 고민하고 답이 안 나와서 구글링 해서 해법을 찾았다.

숫자판에 있는 숫자는 4방향으로 이동 후 다시 탐색할 수 있다.

따라서 방문함수를 따로 만들 필요가 없다.

(0, 0)부터 (N, N)까지 탐색하면서, 가능한 한 모든 6자리 숫자(문자로 된)를 탐색한다.

해당 좌푯값에 있는 문자를 temp에 넣어놓고, 길이가 6이 될 때 까지 돌린다.

재귀에는 다음 갈 x좌표와 y좌표, 그리고 현재 좌표에 있는 값과 temp를 더한 값을

재귀로 호출한다.

그렇게 돌다가 길이가 6이면 set 함수에 만들어 놓은 temp값을 넣어준다.

솔직히 정확히 어떤 식으로 해당 함수가 동작하는지 아직 완전히 이해가 가지 않는다.

이 문제를 기준으로 디버깅 하면서 꼭 동작 방식을 익혀야겠다.