Baekjoon 1987 알파벳 - BackTracking

더 깔끔한 노션을 원한다면

Baekjoon 1987 알파벳 - BackTracking

1987번: 알파벳

설계

1. 배열 범위를 벗어나지 않는지 체크

2. 이미 방문했는지 체크

3. 이미 방문한 알파벳인지 체크

이미 방문한 알파벳인지 체크하는 것이므로 백트래킹을 사용해야 한다.

1. 배열 범위

private boolean isLimit(int r, int c) {
  return r > 0 && c > 0 && r <= R && c <= C;
}

범위를 벗어나면 런타임 에러가 발생하므로 범위 체크를 꼭 해줘야 한다.

2. 방문 여부

private boolean canGo(int r, int c) {
  return !alpha[board[r][c] - 'A'] && !visit[r][c];
}

이미 방문했는지 체크하는 크기가 26인 boolean 배열 alpha

이미 방문한 좌표인지 체크하는 2차원 boolean 배열 visit

이 두 배열을 통해 백트래킹을 진행한다.

백트래킹

private void backTracking(int r, int c, int count) {
  for(int i = 0 ;i<4;i++){
    int nextR = r + dx[i];
    int nextC = c + dy[i];
    if(!isLimit(nextR,nextC) || !canGo(nextR,nextC)){
      if(count > answer){
        answer = count;
      }
      continue;
    } else{
      visit[nextR][nextC] = true;
      alpha[board[nextR][nextC] - 'A'] = true;
      backTracking(nextR,nextC,count+1);
      visit[nextR][nextC] = false;
      alpha[board[nextR][nextC] - 'A'] = false;
    }
  }
}

이미 사용했던 값은 중복되면 안되므로 visit과 alpha을 설정해준다.

backTracking이 종료되면 visit과 alpha을 false로 바꿔주는게 포인트!

answer는 cannotGo일때 바꿔준다.

모음의 개수가 1 이상, 자음의 개수가 2 이상인지 확인해준다.

if(!isLimit(nextR,nextC) || !canGo(nextR,nextC)){
  if(count > answer){
    answer = count;
  }
  continue;
}

isLimit도 canGo 메서드에 넣어줄 수 있다.

전체 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
  public static void main(String[] args) throws Exception {
    Baekjoon solution = new Baekjoon();
    solution.P1987();
  }
}

class Baekjoon {
  char[][] board;
  boolean[][] visit;
  boolean[] alpha = new boolean[26];
  int R, C;
  int answer = Integer.MIN_VALUE;
  int[] dx = { 0, 0, 1, -1 };
  int[] dy = { 1, -1, 0, 0 };

  public void P1987() throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    R = Integer.parseInt(st.nextToken());
    C = Integer.parseInt(st.nextToken());
    visit = new boolean[R + 1][C + 1];
    board = new char[R + 1][C + 1];
    for (int i = 1; i <= R; i++) {
      String str = br.readLine();
      for (int j = 1; j <= C; j++) {
        board[i][j] = str.charAt(j - 1);
      }
    }
    visit[1][1] = true;
    alpha[board[1][1] - 'A'] = true;
    backTracking(1, 1, 1);
    System.out.println(answer);
  }

  private void backTracking(int r, int c, int count) {
    for (int i = 0; i < 4; i++) {
      int nextR = r + dx[i];
      int nextC = c + dy[i];
      if (!canGo(nextR, nextC)) {
        if (count > answer) {
          answer = count;
        }
        continue;
      } else {
        visit[nextR][nextC] = true;
        alpha[board[nextR][nextC] - 65] = true;
        backTracking(nextR, nextC, count + 1);
        visit[nextR][nextC] = false;
        alpha[board[nextR][nextC] - 65] = false;
      }
    }
  }

  private boolean canGo(int r, int c) {
    return isLimit(r,c) && !alpha[board[r][c] - 'A'] && !visit[r][c];
  }

  private boolean isLimit(int r, int c) {
    return r > 0 && c > 0 && r <= R && c <= C;
  }

}