[SWEA] 2819. 격자판의 숫자 이어 붙이기 - JAVA

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD 

SW Expert Academy

풀이

모든 좌표를 다 방문하고 각 좌표마다 백트레킹을 이용하여 문제를 푼다.

7개의 좌표값을 백트레킹을 이용하여 탐색하고 리스트에 넣는다.(4*4이기 때문에 시간초과는 웬만해서는 안난다)

리스트에 넣을 때마다 리스트에 값이 있는지 확인하고 넣게되면 시간초과가 발생한다.

따라서, 먼저 리스트에 넣고 정렬한다음 중복된 개수를 센 다음 리스트의 크기에서 중복된 개수를 빼면 된다.

 

+) HashSet을 이용하면 중복되는 값이 없어지기 때문에 값 추가하여 HashSet의 크기를 구하면 답을 구할 수 있다.

코드

import java.util.*;
import java.io.*;

class Solution {
	static int board[][];
	static int dx [] = {-1, 0, 1, 0};
	static int dy [] = {0, 1, 0, -1};
	static ArrayList<String> list;
	
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
				
		int T = Integer.parseInt(br.readLine());
		for(int test_case = 1; test_case <= T; test_case++)
		{			
			board = new int [4][4];
			list = new ArrayList<>();
			
			for(int i=0;i<4;i++) {
				st = new StringTokenizer(br.readLine());
				for(int j=0;j<4;j++) {
					board[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
			for(int i=0;i<4;i++) {
				for(int j=0;j<4;j++) {
					back(0, i, j, Integer.toString(board[i][j]));
				}
			}
			Collections.sort(list);
			
			int count = 0;
			for(int i=1;i<list.size();i++) {
				if(list.get(i-1).equals(list.get(i))) {
					count++;
				}
			}
			System.out.println("#"+test_case+" "+(list.size()-count));

		}
		
	}
	
	static void back(int cnt, int x, int y, String str) {
		if(cnt == 6) {
			list.add(str);
			return;
		}
		
		for(int i=0;i<4;i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if(nx >= 4 || ny >= 4 || nx < 0 || ny < 0) continue;
			
			back(cnt+1, nx, ny, str+board[nx][ny]);

		}	
		
	}

}