[백준/1987] 알파벳 (Java)

Question

• 문제 이동 링크
• 분류 : DFS(백트레킹)
• 풀이 시간 : 30분

문제 해설

1. R x C인 배열이 존재한다. 이 배열 안에는 하나의 알파벳이 들어가 있다.
2. (0, 0)부터 시작해서 상, 하, 좌, 우 방향으로 움직인다.
3. 다음 칸으로 움직일 때, 이전에 방문했던 칸의 알파벳과 같은 알파벳이 나오면 안된다.
4. 움직일 수 있는 최대의 칸은?

Solution

풀이 접근 방법

1. 말이 최대한 몇 칸을 지날 수 있는지 = DFS(백트레킹)
2. 하나의 알파벳이 담긴 표 모양의 보드 = char 배열 사용
3. 인접한 상, 하, 좌, 우로 이동 가능 = int[] dx, dy 사용하여 이동 제한
4. 이번에 방문했던 알파벤 나오면 안됨 = 나왔던 값들은 Set에 넣어서 확인
   • 방문 확인을 위해 주로 사용하던 boolen 배열 사용할 필요 없음

정답 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashSet;
import java.util.Set;

public class Main_1987 {
  static int C, R;
  static char[][] map;
  static int[] dx = { 0, 0, 1, -1 }, dy = { 1, -1, 0, 0 };
  // 최대 이동 가능한 칸 수를 담는 변수
  static int maxDepth = -1;

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

    R = Integer.valueOf(info[0]);
    C = Integer.valueOf(info[1]);
    map = new char[R][C];

    for (int i = 0; i < map.length; i++) {
      map[i] = br.readLine().toCharArray();
    }

    // 지나왔던 칸의 알파벳을 담고, 다음 이동 시 중복을 막기 위한 Set 사용
    Set<Character> set = new HashSet<Character>();

    set.add(map[0][0]);

    // 전체 map 탐색
    // 말이 지나는 칸은 좌측 상단의 칸도 포하기 때문에 depth는 1부터 시작
    move(0, 0, set, 1);

    bw.write(maxDepth + "\n");
    bw.flush();
    bw.close();
  }

  static void move(int x, int y, Set<Character> set, int depth) {
    for (int i = 0; i < 4; i++) {
      // 새로 이동할 좌표
      int nx = x + dx[i];
      int ny = y + dy[i];

      // 배열의 범위를 벗어난 좌표이거나
      // 이미 이전에 방문을 했거나, 이미 방문한 좌표의 알파벳과 같은 값이라면
      // = 이동할 수 없음
      if (!isIn(nx, ny) || set.contains(map[nx][ny])) {
        // 최대 이동값 갱신 + 다음 좌표 탐색
        maxDepth = Math.max(maxDepth, depth);
        continue;
      }
      
      // 위 조건과 만족하지 않으면 = 해당 칸으로 이동할 수 있음
      // 집합에 알파벳 넣기
      set.add(map[nx][ny]);

      // 다음 칸으로 이동
      move(nx, ny, set, depth + 1);

      // 백트레킹 
      // 다음 좌표로 이동이 끝났으면
      // 기준 좌표에서 다른 방향으로의 이동을 위해 방문했던 알파벳 집합에서 지우기
      set.remove(map[nx][ny]);
    }

  }

  // 배열의 칸 안에 존재하는 좌표인지 확인하는 함수
  static boolean isIn(int x, int y) {
    if (0 <= x && x < R && 0 <= y && y < C) {
      return true;
    }
    return false;
  }

}