[SWEA JAVA] 2105. [모의 SW 역량테스트] 디저트 카페

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

SW Expert Academy

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

public class Solution {
	public static int T, N, ans;
	public static int[][] map;
	public static int[] dx = { 1, 1, -1, -1 };
	public static int[] dy = { 1, -1, -1, 1 };
	public static int[] visited;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		T = Integer.parseInt(br.readLine());
		for (int tc = 1; tc <= T; tc++) {
			// 1. 입력값 받기
			// 1-1. N, ans map
			N = Integer.parseInt(br.readLine());
			map = new int[N][N];
			visited = new int[101];
			ans = -1;

			// 1-2. map 입력
			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. 모든 점에 대해서 dfs visited 초기화
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					
					int nx = i + dx[0];
					int ny = j + dy[0];
					if(nx <0 || ny <0 || nx >= N || ny >= N) continue;
					
					visited[map[nx][ny]] = 1;
					dfs(i, j, nx, ny, 0, 1);
					visited[map[nx][ny]] = 0;
				}
			}

			// 3. 최댓값 계산 출력
			System.out.println("#" + tc + " " + ans);
		}

	}

	public static void dfs(int sx, int sy, int x, int y, int at, int depth) {
		// 2-1. 시작점으로 돌아왔다면 arr의 사이즈 출력 
		if(x == sx && y == sy) {
			
			if(depth>ans) ans = depth;
			
			return;
		}
		for(int i =at;i< 4 && i < at+2;i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if(nx <0 || ny <0 || nx >= N || ny >= N) continue;
			if(visited[map[nx][ny]] == 1) continue;
			
			visited[map[nx][ny]] = 1;
			dfs(sx, sy, nx, ny, i, depth+1);
			visited[map[nx][ny]] = 0;
		}
		
	}
}

 

풀이 사항
풀이 일자: 2024.08.27
풀이 시간: 60분 00초
채점 결과: 정답
예상 문제 유형: DFS

 

풀이 방법

대각선이라서 뭔가 헷갈리지만 그냥 직사각형이라고 생각하고 짜보았다.

 

처음에는 어떻게든 돌아오기만 하면 출력해보자 하고 코드를 짜봤는데 그냥 같던길을 되돌아 오는 경우는 정답에서 제외된다는 문제의 조건이 있기 때문에 dfs안에 for문을 조정해주었다.