[Java] SW Expert Academy 2105번 문제: [모의 SW 역량테스트] 디저트 카페 (DFS, 깊이 우선 탐색)

--- 문제 ---

 

 

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

 

--- 코드 ---

 

해당 문제는 DFS 를 사용하면 되는 문제 입니다.

대신 특이사항이 몇가지 있습니다.

 

• 사각형은 무조건 한가지 방향 흐름으로 그려낼 수 있다는 점
  • 시작점에서 갈 수 있는 모든 방향을 dfs 로 하는 것이 아니라 처음에는 무조건 시작점에서 하우(오른쪽아래)방향으로 움직이고, 그 다음 방향은 하좌 -> 상좌 -> 상우 로 움직이면 되는 것 입니다. 이 점만 잘 파악했다면 쉽게 풀어질 수 있는 문제였습니다.
    (처음에 저는 시작점에서 가능한 모든 대각선 방향으로 움직이게 코드를 작성했다가 처리 시간이 엄청 오래걸리게 되었습니다.)
• 카페 투어 중에 중복되는 디저트 값이 있으면 안되는 것
  • 이것은 Set 자료구조를 이용해서 풀면 됩니다. Set 은 중복되는 값을 허용하지 않는 다는 특성이 있기 때문입니다.
• 방향순서가  0->1->2->3 이라고 했을 때, 3까지 방향이 돌고 다음의 방향이 되는 경우 (현재 코드에서는 4)
  • 이제 4가지 방향을 다 돌았는데도 시작점을 못 돌아온 경우는 사각형을 못만든다는 뜻이므로 투어를 끝내야합니다.

 

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.HashSet;
import java.util.Scanner;

public class Sw2105 {
	
	public static int[][] map;
	public static int max_cnt;
	public static int N;
	public static int[] start = new int[2];
	public static HashSet<Integer> desserts;
	public static boolean[][] visited;
	// 어디서든 방향의 흐름이 같아도 된다는 점
	// 하우, 하좌, 상좌, 상우 
	public static final int[][] DIRECTIONS = {{1,1},{1,-1},{-1,-1},{-1,1}};
	
	public static void main(String[] args) throws FileNotFoundException {
		
		System.setIn(new FileInputStream("./src/2105.txt"));

		Scanner sc = new Scanner(System.in);
		int T;
		T=sc.nextInt();
			
		for(int test_case = 1; test_case <= T; test_case++) {
			
			// 1. Initialize
			N = sc.nextInt();
			map = new int[N][N];
			max_cnt = 0;
			
			for(int i=0; i<N; ++i) {
				for(int j=0; j<N; ++j) {
					map[i][j] = sc.nextInt();
				}
			}
			
			// 2. DFS
			// 마지막 행,열은 할 필요 없음
			for(int i=0; i<N-1; ++i) {
				start[0]=i;
				for(int j=0; j<N-1; ++j) {
					desserts = new HashSet<>();
					start[1]=j;
					visited = new boolean[N][N];
					dfs(i,j,0,0);
				}
			}
			
			// 3. 결과 출력
			max_cnt = (max_cnt<=1)? -1 : max_cnt;
			System.out.printf("#%d %d%n", test_case, max_cnt);
			
		}
			
	}
	
	// 4. DFS 함수
	public static void dfs(int y, int x, int path, int flow) {
		
		// 기저함수 (Basis)
		// 4-1. 이번 자리가 방문한 적이 있으면
		if(visited[y][x]) {
			// 4-1-1. 방문한 적이 있는데 시작점이면
			if(y==start[0] && x==start[1]) {
				// 4-1-1-1. 카페 투어가 잘 완료됐으므로 max 값 비교
				if(path > max_cnt) {
					max_cnt = path;
				}
			}
			// 4-1-2. 방문한 적이 있는데 시작점이 아니면 해당 투어 끝내기
			else {
				return;
			}
		}
		// 4-2. 4방향이 모두 끝났는데, 방문한 적이 있는 곳으로 안 돌아온 경우 투어 끝내기
		else if(flow==DIRECTIONS.length) {
			return;
		}
		
		// 4-3. 현재 디저트 값이 중복되는지 체크
		int current = map[y][x];
		int pre = desserts.size();
		desserts.add(current);
		// 4-3-1. 현재 디저트 넣는데 이전이랑 set 길이가 같으면
		// 중복되는 값이 있다는 뜻이므로 투어 끝내기
		if(pre == desserts.size()) {
			return;
		}
		// 4-3-2. 길이 늘어난거면 해당 자리 방문하기
		visited[y][x] = true;
		
		// 4-4. 같은 방향으로 다음 카페로 넘어가기
		int[] direc = DIRECTIONS[flow];
		int nexty = y+direc[0];
		int nextx = x+direc[1];
		if(nexty>=0 && nexty<N && nextx>=0 && nextx <N) {
			dfs(nexty, nextx, path+1, flow);
		}
		
		// 4-5. 다음 방향으로 다음 카페로 넘어가기
		int next_flow = (flow==3)? 0 : flow+1;
		direc = DIRECTIONS[next_flow];
		nexty = y+direc[0];
		nextx = x+direc[1];
		if(nexty>=0 && nexty<N && nextx>=0 && nextx <N) {
			dfs(nexty, nextx, path+1, flow+1);
		}
		
		// 4-6. 현재 자리 방문 안한걸로 돌려놓기
		visited[y][x] = false;
		desserts.remove(current);
		
		
	}

}

 

--- 출처 ---

 

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

SW Expert Academy