[Java] 2105. 디저트 카페

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

문제 출처:https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5VwAr6APYDFAWu

SW Expert Academy

 

검사 순서(가장 긴 경로를 만드는 것부터 시작)와 visit을 이용한 방문 여부 확인을 통해 해결.

 

전체 소스코드 아래 추가적인 설명이 있습니다.

 

---

1. 전체 소스코드

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

public class Solution {

    static int N;
    static int[][] map;
    static boolean[] visit = new boolean[101];
    static int max;
    static boolean flag;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());

        for (int test_case = 1; test_case <= T; test_case++) {
            StringTokenizer st;

            N = Integer.parseInt(br.readLine());
            map = new int[N][N];

            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());
                }
            }

            max = -1;
            flag = false;

            for (int move = N - 1; move > 1; move--) { // 한 방향으로 이동하는 횟수
                if (flag) {
                    break;
                }
                for (int i = 1; i < move; i++) {
                    int j = move - i;
                    // 오른쪽 위 i번, 오른쪽 아래 j번 왼쪽 아래 i번, 왼쪽 위 j번
                    // move + 1개의 셀을 차지함 시작지점은 처음에 위로 i번 가기 때문에
                    for (int xIdx = i; xIdx <= N - 1 - j; xIdx++) {
                        for (int yIdx = 0; yIdx <= N - 1 - move; yIdx++) {
                            goAround(xIdx, yIdx, i, j);
                        }
                    }
                }
            }

            bw.append("#"+test_case+" "+max+"\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }

    // move 1: right up, move 2: right down, move 3 : left down, move 4 : left up
    private static void goAround(int xIdx, int yIdx, int move1, int move2) {
        Arrays.fill(visit, false);
        int x = xIdx;
        int y = yIdx;
        for (int i = 0; i < move1; i++) {
            if (!visit[map[x][y]]) {
                visit[map[x--][y++]] = true;
            }
            else
                return;
        }
        for (int i = 0; i < move2; i++) {
            if (!visit[map[x][y]]) {
                visit[map[x++][y++]] = true;
            }
            else
                return;
        }
        for (int i = 0; i < move1; i++) {
            if (!visit[map[x][y]]) {
                visit[map[x++][y--]] = true;
            }
            else
                return;
        }
        for (int i = 0; i < move2; i++) {
            if (!visit[map[x][y]]) {
                visit[map[x--][y--]] = true;
            }
            else
                return;
        }
        if (max < (move1 + move2) * 2) {
            max = (move1 + move2) * 2;
            flag = true;
        }

    }

}

 

---

2. 풀이

이동할 수 있는 방향에 따라 횟수를 구분하였다. 오른쪽 위 방향으로 이동하는 횟수를 move1, 오른쪽 아래 방향으로 이동하는 횟수를 move2라고 할 때, 경로가 사각형이어야 하기 때문에 대칭적으로 왼쪽 아래로 이동하는 횟수는 move1, 왼쪽 위로 이동하는 횟수는 move2와 같게 된다. 길이 N의 지도에서 이동할 수 있는 최대 횟수는 N-1번이다. move1 + move2 = move라고 할 때 move를 N-1부터 2 사이의 값으로 지정하여 move1과 move2를 각각 설정 후 모든 시작 가능한 지점에 대하여 탐색을 시작해준다.

max = -1;
flag = false;

for (int move = N - 1; move > 1; move--) { // 한 방향으로 이동하는 횟수
  if (flag) {
    break;
  }
  for (int i = 1; i < move; i++) {
    int j = move - i;
    // 오른쪽 위 i번, 오른쪽 아래 j번 왼쪽 아래 i번, 왼쪽 위 j번
    // move + 1개의 셀을 차지함 시작지점은 처음에 위로 i번 가기 때문에
    for (int xIdx = i; xIdx <= N - 1 - j; xIdx++) {
      for (int yIdx = 0; yIdx <= N - 1 - move; yIdx++) {
        goAround(xIdx, yIdx, i, j);
      }
    }
  }
}

탐색을 시작하면 방문한 디저트 카페를 체크하기 위해 visit을 초기화하여 이동방향에 따라 디저트 카페의 값을 검사하여 방문을 기록한다. 한 번이라도 중복된다면 바로 탐색을 중단한다. 마지막까지 중복된 카페가 없다면 max값을 갱신한 후 플래그를 true로 만든다. 검사를 가장 큰 사각형부터 시작하기 때문에 한 번이라도 성공한다면 이후에 만들어진 경로의 방문 가게 수는 적거나 같기 때문에 검사할 필요가 없다.

// move 1: right up, move 2: right down, move 3 : left down, move 4 : left up
private static void goAround(int xIdx, int yIdx, int move1, int move2) {
  Arrays.fill(visit, false);
  int x = xIdx;
  int y = yIdx;
  for (int i = 0; i < move1; i++) {
    if (!visit[map[x][y]]) {
      visit[map[x--][y++]] = true;
    }
    else
      return;
  }
  for (int i = 0; i < move2; i++) {
    if (!visit[map[x][y]]) {
      visit[map[x++][y++]] = true;
    }
    else
      return;
  }
  for (int i = 0; i < move1; i++) {
    if (!visit[map[x][y]]) {
      visit[map[x++][y--]] = true;
    }
    else
      return;
  }
  for (int i = 0; i < move2; i++) {
    if (!visit[map[x][y]]) {
      visit[map[x--][y--]] = true;
    }
    else
      return;
  }
  if (max < (move1 + move2) * 2) {
    max = (move1 + move2) * 2;
    flag = true;
  }
}