🔑SWEA_SW_2105

📁 [SW_2105] 디저트 카페

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

public class Solution {
	static int N;
	static int[][] map;
	static int dx[] = { 1, -1, -1, 1 };
	static int dy[] = { 1, 1, -1, -1 };
	static boolean[][] v;
	static boolean[] dessert;
	static int max;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();

		int tc = Integer.parseInt(br.readLine());

		for (int T = 1; T <= tc; T++) {
			sb.append("#").append(T).append(" ");

			// 한 변의 길이
			N = Integer.parseInt(br.readLine());
			map = new int[N][N];
			max = 0;

			// 디저트 종류 입력
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				for (int j = 0; j < N; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
				}
			}

			// 양옆과 밑에 2칸이 있어야 사각형이 가능 서치
			for (int i = 0; i < N - 2; i++) {
				for (int j = 1; j < N - 1; j++) {
					v = new boolean[N][N];
					// 디저트 종류
					dessert = new boolean[101];
					// 방문 처리
					v[i][j] = true;
					// 디저트 방문처리
					dessert[map[i][j]] = true;
					dfs(1, i, j, i, j, 0);
				}
			}
			if (max == 0) {
				sb.append("-1").append("\n");
			} else {
				sb.append(max).append("\n");
			}
		}
		System.out.println(sb);
	}

	// dfs - prevD는 이전방향
	static void dfs(int cnt, int y, int x, int initY, int initX, int prevD) {
		for (int i = prevD; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];

			// 범위에 벗어나지 않으면
			if (ny >= 0 && ny < N && nx >= 0 && nx < N) {
				// 초기 상태로 돌아왔을 때 종료 ( 기저조건 )
				if ((ny == initY) && (nx == initX) && cnt > 2) {
					max = Math.max(max, cnt);
					return;
					// 종료
				}
				// 방문하지 않은 곳이면
				if(!v[ny][nx] && !dessert[map[ny][nx]]) {
					// 방문 처리
					v[ny][nx] = true;
					dessert[map[ny][nx]] = true;
					dfs(cnt + 1, ny,nx,initY,initX,i);
					// 백트래킹
					v[ny][nx] = false;
					dessert[map[ny][nx]] = false;
				}
			}
		}
	}
}

🤔 나의 생각

처음엔 이 문제에 대한 접근을 잘못했다..
스터디에서 푼 것인데 정사각형 탐색과 직사각형 탐색을 나눠서 생각하며 머리를 팽글돌리며 생각했지만 못풀어서..
스터디원들의 설명을 들을때 dfs를 듣자마자 아..! 라는 생각이 들었다..
그래서 사각형을 벗어나는 범위를 제외하고 완전 탐색으로 모든 점에서의 출발로 하여 사각형을 만들었다.
dfs 매개변수로 움직인 횟수, 좌표, 초기좌표, 이전 방향 을 체크해서 초기좌표로 왔을 때 끝을 내고 방향은 전에 방향에 가지 못하게 for문을 구성했다.
그리고 dfs를 통해 최대 디저트 종류를 구해 출력해 주었다.
뭔가 오랜만에 풀다보니 여러 생각을 못한 것같다.. 틀린 것 같으면 빠르게 다양한 생각을 하자 !!