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

문제

• SWEA 2105
• 문제의 저작권은 SW Expert Academy에 있습니다.

접근방식

DFS로 먹을 수 있는 디저트 경로를 따라가면 되므로 쉽게 생각했지만, 코드를 작성하다가 중간에 디저트를 언제 먹을지 처리해주는 과정에서 시간이 오래 걸린 문제이다.
해결한 접근 방법은 다음과 같다.

1. 2중 for문을 돌면서 각 좌표를 시작점 startI, startJ로 두고 디저트 경로를 찾는 go()함수를 호출한다.
   1-1. 1개~100개 까지의 디저트 개수를 인덱스로 하는 foods배열을 만든다. 1-2. 사각형을 만들기 위한 방향은 ‘오른쪽 아래 대각선→왼쪽 아래 대각선→왼쪽 위 대각선→오른쪽 위 대각선’ 순으로 정하고 각 방향 정보를 담는 di, dj배열을 만들어서 인덱스 0,1,2,3으로 둔다. 처음 함수를 호출할 때 방향을 0으로 해서 go(startI, startJ, 0, 1)로 셋팅한다.
2. go()함수
   2-1. 현재 온 좌표에서 디저트를 먹었음을 foods배열에 표시한다.
   2-2. 현재 방향으로 다음 좌표인 ni,nj를 구해서 범위 안에 있는지 그리고 아직 먹지 않은 디저트인지를 확인한다.
   2-3. 2-2조건을 만족하면 먹은 디저트를 관리하는 sum을 하나 증가시켜서 go(ni, nj, dir, sum+1)를 재귀호출해 ni,nj에서 직진한다.
   2-4. 만약 직진으로 더 갈 수 없는 경우 2-3에서 함수를 호출한 곳으로 다시 돌아오므로 ni, nj에서 다음방향으로 이동하기 위해 go(ni, nj, dir+1, sum+1)를 호출한다.
   2-5. 만약 다음 방향으로도 더 갈 수 없는 경우 2-4에서 함수를 호출한 곳으로 돌아온다. 이때, map[ni][nj]의 디저트트 먹을수 없기 때문에 다시 map[ni][nj] = false를 처리해주어야 한다.
   2-6. 재귀를 통해 마지막에 출발점으로 다시 돌아오면 Ans와 sum을 비교해 최대값을 Ans에 저장해주고 리턴한다.

나는 2-5번의 조건을 생각하지 못했는지 그림을 그려보면 아래 경우에 꼭 필요한 조건이다.

교수님이 항상 강조하시는것 처럼 계획을 세우고 항상 내 계획의 허점에 대해 스스로 공격해보고 이를 방어해보는 습관을 들이자.

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Solution {
	
	static int T;
	static int N;
	static int[][] map;
	static boolean[] foods;
	static StringTokenizer st;
	static int startI, startJ;
	static int[] di = {1, 1, -1, -1};
	static int[] dj = {1, -1, -1, 1};
	static int Ans;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		T = Integer.parseInt(br.readLine());
		for(int tc=1; tc<=T; tc++) {
			N = Integer.parseInt(br.readLine());
			map = new int[N][N];
			Ans = -1;
			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());
				}
			}//input
			
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					startI = i;
					startJ = j;
					foods = new boolean[101]; //디저트 1번~100번
					go(startI, startJ, 0, 1);
				}
			}
			bw.write("#"+tc+" "+Ans);
			bw.newLine();
		}
		bw.flush();
		bw.close();
		br.close();
	}

	private static void go(int i, int j, int dir, int sum) {
		foods[map[i][j]] = true; //간식 먹음
		if(dir >= 4) return;
		//다음 방향
		int ni = i + di[dir];
		int nj = j + dj[dir];
		if(ni == startI && nj==startJ) {
			Ans = Math.max(Ans, sum);
			return;
		}
		//다음 좌표로 갈 수 있는지
		if(ni >= 0 && ni < N && nj >= 0 && nj < N && !foods[map[ni][nj]]) {
			if(foods[map[ni][nj]]) return;
			foods[map[ni][nj]] = true;
			go(ni, nj, dir, sum+1); //현재 방향으로 다음 좌표 ㄱㄱ
			go(ni, nj, dir+1, sum+1); //다음 방향으로 다음 좌표 ㄱㄱ
			foods[map[ni][nj]] = false; //다음 좌표로 가지 않는 케이스 고려하기 위해
		}
	}
}