[SWEA] 7699번 / Java / 수지의 수지 맞은 여행

문제 - (https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWqUzj0arpkDFARG&categoryId=AWqUzj0arpkDFARG&categoryType=CODE)

전형적인 dfs 문제였다

dy,dx를 이용한 4방 탐색을 사용했다

한번 방문했던 곳에서 본 명물을 visited에 추가하고, 다음번 방문 하는 곳에 봤던 명물이 있다면 그 곳은 방문하지 않는다

---

📌주의할 점

• visited처리를 어떻게 할까 고민하다가 처음엔 ArrayList를 사용했다. 리스트에 add, remove를 사용하려고 했는데 문제가 생겼다. ArrayList<char>형 리스트의 경우 list.remove( map[y][x] ) 를 하게되면 char 자체가 제거되는 것이 아니라 map[y][x]가 index로 인식돼 버리는 문제가 생긴다. 만약 내가 원하는대로 하려면 ArrayList<Character>형 리스트를 사용해야 한다. 왜냐면 char타입은 primitive(기본형) 타입이기 때문에 객체가 아니기에, 내부적으로 equals 처리를 지원하지 않기 때문이다.
• 그렇다면 어떻게 해야할까? 내가 아이디어를 생각해내기 전까지 생각한 과정은 이렇다.
  1. 명물은 char형 데이터이고 A~Z까지 이다.
  2. A~Z를 인덱스로 하는 visited 배열을 만들면 되지 않을까?
  3. boolean[] visited = new boolean['Z'+1] << 0부터 'Z'까지 길이의 배열 생성
  4. visited[ map[y][x] ] = true << 이와같은 형태로 visited 처리를 하면 된다.

---

😅실수

• 이런식의 문제에서 항상 하는 실수인데, 첫 dfs 함수 호출 시에 전달하는 인자에 주의해야 한다. dfs(0,0,0)으로 보내면 수지가 0,0위치부터 여행을 시작한다는 뜻인데, 그렇게되면 0,0은 방문된 것으로 쳐야 하므로 0,0,1이 파라미터가 되어야 한다.
• 기저사례가 존재하는 dfs함수 모양에 익숙해서 dfs를 호출하는 바로 위아래에 visited = true, false 처리를 하는게 습관이 되어버렸는데, 이 문제같은 경우는 dfs 함수에 들어온 첫 시점부터 y,x 위치를 "방문"했다는 의미가 되므로 for문 밖에서 현재 위치를 visited 처리해 주어야 한다. visited false처리도 물론 for문 밖에서!

 

---

코드

package algorithm.swea.D4;

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

/**
 * 1:20~1:52
 */
public class _7699_SuzyTrable {
    static int R, C;
    static char[][] map;
    static int[] dy = {-1, 1, 0, 0};
    static int[] dx = {0, 0, -1, 1};
    static boolean[] visited;
    static int answer = 0;

    static void dfs(int y, int x, int cnt) {
        visited[map[y][x]] = true;
        answer = Math.max(answer, cnt);
        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (ny < 0 || nx < 0 || ny >= R || nx >= C || visited[map[ny][nx]]) continue;
            dfs(ny, nx, cnt + 1);
        }
        visited[map[y][x]] = false;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

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

        for (int tc = 1; tc <= T; tc++) {
            st = new StringTokenizer(br.readLine());
            R = Integer.parseInt(st.nextToken());
            C = Integer.parseInt(st.nextToken());
            map = new char[R][C];
            answer = Integer.MIN_VALUE;
            visited = new boolean['Z' + 1];
            for (int i = 0; i < R; i++) {
                map[i] = br.readLine().toCharArray();
            }
            dfs(0, 0, 1);
            sb.append("#").append(tc).append(" ").append(answer).append("\n");
        }
        System.out.print(sb);
    }
}