SWEA - 격자판의 숫자이어붙이기

1) 문제과정

1. 동서남북 네 방향으로 인접한 격자로 총 여섯 번 이동한다

2. 각 칸에 적혀있는 숫자를 차례대로 이어 붙이면 7자리의 수가 되는 갯수를 구하라

 

2) 문제 풀이

1. 7자리의 수가 될때까지 4방향으로 탐색하며 이동한다.

2. 7자리가 되면 set에 저장한다.

3. 계속 반복

 

3) 느낌점

- 이 문제에서 dfs 사용하는것과 hashset 알고있는지가 중요한것같다. 7자리의 수 중에 중복체크를 하기 위해 hashset 사용하였는데, set를 몰랐다면 푸는데 어려움이 있었을것같다.

 

import java.util.HashSet;
import java.util.Scanner;

public class Solution_격자판의숫자이어붙이기 {
	static int answer = 0;
	static int map[][] = new int[4][4];
	static HashSet<String> HS = new HashSet<>();

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

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int test_case = 1; test_case <= T; test_case++) {
			for (int y = 0; y < 4; y++) {
				for (int x = 0; x < 4; x++) {
					map[y][x] = sc.nextInt();
				}
			}

			for (int y = 0; y < 4; y++) {
				for (int x = 0; x < 4; x++) {
					DFS(y, x, "");
				}
			}
			answer = HS.size();
		
			System.out.println("#" + test_case + " " + answer);
			answer = 0;
			HS.clear();
		}
	}

	public static void DFS(int y, int x, String string) {
		if (string.length() == 7) {
			HS.add(string);
			return;
		} else {
			for (int k = 0; k < 4; k++) {
				int ny = y + dy[k];
				int nx = x + dx[k];
				if (ny >= 0 && nx >= 0 && ny < 4 && nx < 4) {
					DFS(ny, nx, string + map[ny][nx]);
				}
			}
		}

	}
}