[SWEA 2105] 디저트 카페 (Java)

SWEA 2105 디저트 카페

문제풀이

조건을 착실히 따르면 DFS로 어렵지않게 풀 수 있는 문제다.

• 대각선 방향으로 움직이고 사각형 모양을 그리며 출발한 카페로 돌아와야 한다.
  • 사각형만을 이루게 하기 위해서는 재귀함수에 이전 진행 방향을 인수로 넘겨주고 그 이상의 방향으로만 진행되도록 하면 된다.
• 카페 투어 중에 같은 숫자의 디저트를 팔고 있는 카페가 있으면 안 된다.
  • HashSet을 이용해서 먹은 디저트를 기록한다.
• 하나의 카페에서 디저트를 먹는 것도 안 된다. 그리고 왔던 길을 다시 돌아가는 것도 안 된다.
  • 방문체크를 한다.

일반적으로 재귀함수를 구현할 때 다음과 같은 형태로 구현하는 것이 일반적이나

	function recursion() {
            if(종료조건){...}

            현재 깊이에서의 수행
    	}

이 문제에서는 현재 깊이에서의 수행 안에 종료조건을 배치하는 것이 시작점을 다시 방문해야하는 상황에서의 set과 방문체크 처리를 하기에 용이했다.

	function recursion() {
           	현재 깊이에서의 수행 {
            		if(종료조건){...}
            	}
    	}

구현코드

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

public class Solution {
	
	static HashSet<Integer> set;
	static int[][] dir = {{1, 1}, {1, -1}, {-1, -1}, {-1, 1}};
	static boolean[][] visited;
	static int[][] map;
	static int N, T, ans, cnt;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		T = Integer.parseInt(br.readLine());
		
		for(int t = 1; t <= T ; ++t) {
			N = Integer.parseInt(br.readLine());
			
			set = new HashSet<>();
			map = new int[N][N];
			visited = new boolean[N][N];
			ans = -1;
			
			for(int r = 0 ; r < N ; ++r) {
				st = new StringTokenizer(br.readLine());
				for(int c = 0 ; c < N ; ++c) {
					map[r][c] = Integer.parseInt(st.nextToken());
				}
			}
			
			for(int r = 0 ; r < N - 2 ; ++r) {
				for(int c = 1 ; c < N - 1 ; ++c) {
					init();
					set.add(map[r][c]);
					visited[r][c] = true;
					tour(r, c, r, c, 0);
					visited[r][c] = false;
					set.remove(map[r][c]);
				}
			}
			
			System.out.println("#" + t + " " + ans);
		}
	}

	private static void tour(int cr, int cc, int sr, int sc, int curve) {
		for(int d = curve ; d < 4 ; ++d) {
			int nr = cr + dir[d][0];
			int nc = cc + dir[d][1];
			
			if(set.size() >= 3 && nr == sr && nc == sc) {
				cnt = set.size();
				ans = cnt > ans ? cnt : ans;
				return;
			}

			if(nr < 0 || nr >= N || nc < 0 || nc >= N || visited[nr][nc]) continue;
			if(set.contains(map[nr][nc])) continue;
			
			visited[nr][nc] = true;
			set.add(map[nr][nc]);
			tour(nr, nc, sr, sc, d);
			set.remove(map[nr][nc]);
			visited[nr][nc] = false;
		}
		
	}

	private static void init() {
		set.clear();
		
		for(int r = 0 ; r < N ; ++r) {
			for(int c = 0 ; c < N ; ++c) {
				visited[r][c] = false;
			}
		}
	}
}