[Java] swea 2105 디저트카페

[Java] swea 2105 디저트카페

 

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5VwAr6APYDFAWu&categoryId=AV5VwAr6APYDFAWu&categoryType=CODE&problemTitle=sw&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=2

SW Expert Academy

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 모의SW_2105_디저트카페 {
	static int N, MAX;
	static int[][] map;
	static int startx, starty;
	static boolean[] selected;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for (int testcase = 1; testcase <= T; testcase++) {
			MAX = 0;
			N = Integer.parseInt(br.readLine());
			map = new int[N][N];
			int maxVal = 0;
			for (int i = 0; i < N; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				for (int j = 0; j < N; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
					if(maxVal < map[i][j]) maxVal = map[i][j];
				}
			}
			selected = new boolean[maxVal+1];
			
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					startx = i;
					starty = j;
					solve(i, j, 0, 0);
				}
			}
			
			System.out.println("#" + testcase  + " " + (MAX == 0 ? -1 : MAX));
		} //tc
		
	} //main
	
	static int[][] dir = new int[][] { {1, 1},{1, -1},{-1, -1},{-1, 1} };
	static void solve(int x, int y, int cnt, int curD) {
		if(x < 0 || x >= N || y < 0 || y >= N) return;

		if(cnt > 1 && x == startx && y == starty) {
			if(MAX < cnt) MAX = cnt;
			return;
		}
		
		for (int d = curD; d <= curD+1; d++) {
			if(d > 3) break;
			int nx = x + dir[d][0];
			int ny = y + dir[d][1];
			
			if(nx >= 0 && nx < N && ny >= 0 && ny < N && !selected[map[nx][ny]]) {
				selected[map[nx][ny]] = true;
				solve(nx, ny, cnt+1, d);
				selected[map[nx][ny]] = false;
			}
		}
	} //solve
}

dir 배열에 대각선 4개 방향을 입력한다.

출발은 무조건 현재 내가 온 방향 혹은 내가 온 방향+1 인덱스만 가능하게 했다.

난 무조건 시계방향으로 사각형을 만들게 했기 때문에 출발을 0으로 했다면 다시 출발지로 돌아올 땐 방향3으로 돌아오면 되니까!!

 

그리고 그냥 dfs 돌리면 된다. 이 때 selected 배열로 이미 뽑힌 숫자인지(디저트인지) 확인만 해주면됨~!