[Java] SWEA 디저트 카페

1. 문제분석

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

SW Expert Academy

디저트 카페를 가는데 위와 같은 조건으로 사각형을 돈다.

단, 갔던 디저트 카페(번호가 같은)는 가지 않을때 최대한 많은 디저트 카페의 개수를 구하는 것이다.

경로를 기억해서 간다 -> 당연히 DFS로 풀 생각을 했고 경로를 하우 -> 하좌 -> 상좌 -> 상우 식으로 고정했다.

2. 시행착오

필자는 처음에 인덱스 오류가 난다 -> 방향을 바꿔야 한다 -> DFS 재귀 처리를 생각해냈다.

다음으로 방향을 고정(하우가 끝나면 더이상 하우는 안함)하기 위해 델타탐색에서 i값을 start로 대체했다.

또한 다 돌았을 경우, 즉 start가 3이고 visited가 true라면 현재까지의 간 거리를 구해냈다.

 

조건이 중복되는 경우가 많아서 나누기 힘들었다.

start가 3이거나 visited가 true인경우, 또 인덱스 오류 났을때가 애매했다.

다시 한 번 생각해보니 내가 방문한 위치(2차원 map을 가진 visited)를 구현해야할까? 싶었다.

내가 먹은 디저트만 기억해내면 되는 것이니 1차원 배열(1~100을 가질 수 있는) 배열을 통해 검사를 했다.

 

또한 재귀를 타고 들어와 같은 방향을 갔을때가 애매해 졌다.

필자는 전에 있던 위치를 매개변수로 줘서 만약 다시 돌아온 경우는 다른 루트로 갈 수 없게 만들었다.

3. 구현

import java.util.*;
import java.io.*;

public class Solution {

    static int answer;
    static int size;
    static int[][] map;
    //우하 -> 좌하 -> 상좌 -> 상우
    static int[] dx = {1, -1, -1, 1};
    static int[] dy = {1, 1, -1, -1};
    //먹은것을 기억하는 배열
    static boolean[] visited;
    //출발점
    static int startX, startY;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());
        for (int c = 1; c <= tc; c++) {
            size = Integer.parseInt(br.readLine());
            map = new int[size][size];
            answer = -1;
            for (int i = 0; i < size; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for (int j = 0; j < size; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            for (int i = 0; i < size - 2; i++) {
                for (int j = 1; j < size - 1; j++) {
                    //dfs
                    startX = j;
                    startY = i;
                    visited = new boolean[101];
                    visited[map[i][j]] = true;
                    dfs(j, i, j, i, 1, 0);
                }
            }

            System.out.println("#" + c + " " + answer);
        }
    }

    static void dfs(int x, int y, int preX, int preY, int cnt, int start) {
        for (int i = start; i < 4; i++) {
            int mx = x + dx[i];
            int my = y + dy[i];

            //인덱스 오류
            if (mx < 0 || my < 0 || mx >= size || my >= size) continue;
            //재귀가 실행되고 만약 지난 경로가 같다면 패스
            if (preX == mx && preY == my) continue;

            //출발점과 동일하다면
            if (startX == mx && startY == my) {
                //검사
                answer = Math.max(cnt, answer);
                return;
            }
            //방문여부를 여기서 처리한건 위의 코드때문
            if (visited[map[my][mx]]) continue;

            //방문 처리
            visited[map[my][mx]] = true;
            dfs(mx, my, x, y, cnt + 1, i);
            visited[map[my][mx]] = false;
        }
    }
}

정리해보자면 다음과 같다.

 

1. DFS를 활용하여  정해둔 방향으로 델타탐색한다.

2. 만약 인덱스 오류거나, 내가 직전에 갔던 방향(하우 -> 하좌 식으로 방향을 고정해야함)이면 continue

3. 시작한 점으로 다시 돌아왔다면 현재까지 들린 디저트 카페의 수를 반환한다.

4. 먹은 디저트라면 continue를 한다(위에서 시작점으로 돌아온다는 조건때문에 여기서 구현)

5. 방문처리, 재귀처리

4. 마무리

조건을 왜이리 어렵게 생각했나 싶다.

너무 중복되니까 나누기가 힘들었고 초기값과 전값을 기억해내니 편하게 구현했다.