[SWEA] 7699번 수지의 수지 맞는 여행

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWqUzj0arpkDFARG&categoryId=AWqUzj0arpkDFARG&categoryType=CODE

SW Expert Academy

---

1. 이해하기

• 상하좌우로 이동이 가능하지만 같은 명물을 보지 않고 가장 많은 명물을 보는 방법을 찾는 것이다.
• dfs로 풀 수 있다.

---

2. 구현하기

• dfs(x,y,depth)
  • 현재 위치를 받고 얼마나 많은 명물을 봤는 지를 갱신해준다.
  • 현재 위치의 명물은 본 것이므로 봤다고 표시를 해준다.
  • 함수가 종료될 때는 다시 보지 않았다고 표시를 해줌으로 다음에 방문을 할 수 있도록 해준다.
  • 이때 ans가 26이 되면 더이상 보지 않고 return을 해준다. 그 이유는 알파벳은 총 26개가 있고 그 이상을 볼 수 없기 때문이다.

static int[] dx = { 0, 0, 1, -1 }, dy = { 1, -1, 0, 0 };
    static boolean[] alpha;
    static int ans = 0;

    static void dfs(int x, int y, int depth) {
        if (ans < depth)
            ans = depth;
        if(ans == 26) return;
        alpha[map[x][y]-'A'] = true;

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (OOB(nx, ny) || alpha[map[nx][ny] - 'A'])
                continue;
            dfs(nx, ny, depth + 1);
        }
        alpha[map[x][y] - 'A'] = false;
    }

---

3. 전체코드

package algo;

import java.util.Scanner;

public class Acm7699_수지의수지맞는여행 {
    static int T, R, C;
    static char[][] map;
    static StringBuilder sb;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        sb = new StringBuilder();
        T = sc.nextInt();
        for (int tc = 1; tc <= T; tc++) {
            R = sc.nextInt();
            C = sc.nextInt();
            map = new char[R][C];
            for (int r = 0; r < R; r++)
                map[r] = sc.next().toCharArray();

            ans = 0;
            alpha = new boolean[26];
            dfs(0, 0, 1);
            sb.append("#" + tc + " " + ans+"\n");
        }
        System.out.println(sb);
        sc.close();
    }

    static int[] dx = { 0, 0, 1, -1 }, dy = { 1, -1, 0, 0 };
    static boolean[] alpha;
    static int ans = 0;

    static void dfs(int x, int y, int depth) {
        if (ans < depth)
            ans = depth;
        if(ans == 26) return;
        alpha[map[x][y]-'A'] = true;

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (OOB(nx, ny) || alpha[map[nx][ny] - 'A'])
                continue;
            dfs(nx, ny, depth + 1);
        }
        alpha[map[x][y] - 'A'] = false;
    }

    static boolean OOB(int x, int y) {
        return x < 0 || x >= R || y < 0 || y >= C;
    }
}

---

4. 배운점

• 나올 수 있는 모든 경우를 보고 최대값이 그 값이 되었을 때 바로 함수를 종료해주면 시간을 많이 단축시킬 수 있다. 이 점을 잘 활용하여 시간단축을 더 할 수 있을지 알아봐야겠다.