[Java] SWEA 2819번 격자판의 숫자 이어 붙이기

SW Expert Academy

---

풀이

DFS를 이용해서 완전탐색을 하고 문제에서 주어진 조건대로 길이가 7인 문자열만 Set에 넣어 중복을 없에 총 개수를 구해 해결했습니다.

---

코드

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

public class Solution {
	public static int[][] board = new int[4][4];
	public static Set<String> set;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder("");
		StringTokenizer st = null;
		
		int T = Integer.parseInt(br.readLine());
		
		for (int tc = 1; tc <= T; ++tc) {
			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());
				}
			}
			
			set = new HashSet<String>();
			
			for (int i = 0; i < 4; ++i) {
				for (int j = 0; j < 4; ++j) {
					go(i, j, 0, Integer.toString(board[i][j]));
				}
			}
			
			sb.append("#").append(tc).append(" ").append(set.size()).append("\n");
		}
		
		System.out.println(sb);
	}
	
	public static void go(int y, int x, int cnt, String s) {
		if (cnt == 6) {
			if (s.length() == 7) {
				set.add(s);
			}
			
			return;
		}
		
		if (y - 1 >= 0) {
			go(y - 1, x, cnt + 1, s + Integer.toString(board[y - 1][x]));
		}
		if (y + 1 < 4) {
			go(y + 1, x, cnt + 1, s + Integer.toString(board[y + 1][x]));
		}
		if (x - 1 >= 0) {
			go(y, x - 1, cnt + 1, s + Integer.toString(board[y][x - 1]));
		}
		if (x + 1 < 4) {
			go(y, x + 1, cnt + 1, s + Integer.toString(board[y][x + 1]));
		}
	}
}

---

pyo7410/Algorithm