[SW expert Academy] SWEA 2819번 격자판의 숫자 이어 붙이기 자바(Java)

[D4] 격자판의 숫자 이어 붙이기 - 2819

문제 링크

성능 요약

메모리: 88,128 KB, 시간: 292 ms, 코드길이: 1,163 Bytes

제출 일자

2023-11-18 15:07

출처: SW Expert Academy, https://swexpertacademy.com/main/code/problem/problemList.do

1. 4x4 격자판을 받음(배열 생성)

2. 동서남북 이동 가능(방향 벡터 사용, 인덱스 밖에 벗어나는지 확인하기)

3. 겹치는게 있을 수 있으므로 set에 넣어준다.

4. 각 출발점을 기준으로 dfs를 호출함(depth == 7 까지)

5. 시간 초과일 수 있지만 배열의 크기가 4x4밖에 안돼서 시간 초과 걱정 x

import java.util.*;

class Solution {
	static int[][] map;
	static HashSet<String> answer;
	static int[] dirX = { -1, 1, 0, 0 };
	static int[] dirY = { 0, 0, -1, 1 };
	static char[] value;

	public static void main(String args[]) throws Exception {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();

		for (int tc = 1; tc <= T; tc++) {
			map = new int[4][4];
			answer = new HashSet<>();
			value = new char[7];
			for (int i = 0; i < 4; i++) {
				for (int j = 0; j < 4; j++) {
					map[i][j] = sc.nextInt();
				}
			}
			for (int i = 0; i < 4; i++) {
				for (int j = 0; j < 4; j++) {
					dfs(i, j, 0);
				}
			}
			System.out.println("#" + tc + " " + answer.size());
		}
	}

	private static void dfs(int x, int y, int depth) {
		if (depth == 7) {
			answer.add(new String(value));
			return;
		}
		value[depth] = (char) (map[x][y] + '0');
		for (int i = 0; i < 4; i++) {
			int nx = x + dirX[i];
			int ny = y + dirY[i];
			if (nx < 0 || nx >= map.length || ny < 0 || ny >= map[nx].length) {
				continue;
			}
			char tmp = value[depth];
			value[depth] = (char) ('0' + map[nx][ny]);
			dfs(nx, ny, depth + 1);
			value[depth] = tmp;
		}
	}
}