BOJ_1987_알파벳문제

이번에는 알파벳 문제를 풀어볼텐데, 이는 기존 BFS문제의 전형적인 문제이며 BackTracking을 활용한 문제입니다.

보통 재귀함수로 BFS를 구현한다면 BackTracking을 한다고 생각하시면 될 것 같습니다.

[문제]

문제를 확인해보면, 알파벳으로 이루어진 배열 하나와 해당 위치를 지났는지 체크하는 

배열을 만들면 될 것 같다는 생각이 듭니다.

처음에는 2,4가 2행 4열을 나타낸다고 생각하여 CAAB와 ADCB는 아래와 같다고 생각했습니다.

C A A B

A D C B 

2x4 행렬 

그치만 자바에서는 굳이 다음과 같이 구현할 필요가 없었습니다. 

1차원 배열에 CAAB와 ADCB를 다 넣어두고 이를 charAt함수를 이용하여 각 요소들을 찾아가면 되기 때문입니다.

CAAB와 ADCB를 담는 배열 하나를 만듭니다.

이 후에는 해당 위치를 지났는 지에 대한 여부를 파악하는 check 함수를 만듭니다. 

(함수로도 만들 수 있지만 여기서는 boolean 배열로 만들어서 구현하였습니다)

여기서 배열의 인덱스는 어떻게 줄 것인가 고민하게 되는데, 알파벳을 그대로 살려서 진행하려면 Map 함수를 사용해도 되는데, 그렇게 하면 너무도 복잡해집니다.

따라서 알파벳에 대한 boolean 배열의 인덱스를 만들기 위해 아스키코드를 사용할 것입니다.

찾아가는 위치에 대한 알파벳에 A를 뺀다면 아스키코드 상 boolean 배열이 완성될 것 입니다.

코드는 다음과 같습니다.

---

public static void main(String[] args) {

// TODO Auto-generated method stub

scanner = new Scanner(System.in);

int xNum = scanner.nextInt();

int yNum = scanner.nextInt();

scanner.nextLine();

String[] board = new String[xNum];

for (int i = 0; i < xNum; i++) {

board[i] = scanner.nextLine();

}

boolean check[] = new boolean[26]; // 알파벳 26개

check[board[0].charAt(0) - 'A'] = true; // 처음 시작 부분은 출발지점이기 때문에 이미 방문했다고 가정

int answer = alphabet(board, check, 0, 0);

System.out.println(answer);

}

---

boolean 배열은 26으로 둔 이유는 알파벳의 갯수 만큼 만들어야하므로 다음과 같이 진행하였습니다.

처음 시작은 0,0이기 때문에 해당 위치는 이미 시작했다고 가정하고 true로 잡습니다.

이 후에는 alphabet함수를 0,0부터 시작한다면서 호출합니다.

alphabet 코드는 다음과 같습니다.

---

private static int alphabet(String[] board, boolean[] check, int x, int y) {

int ans = 0;

for (int i = 0; i < 4; i++) {

int nx = x + dx[i];

int ny = y + dy[i];

if ((nx >= 0 && nx < board.length) && (ny >= 0 && ny < board[0].length())) {

if (check[board[nx].charAt(ny) - 'A'] == false) {

check[board[nx].charAt(ny) - 'A'] = true;

int next = alphabet(board, check, nx, ny);

if (ans < next)

ans = next;

check[board[nx].charAt(ny) - 'A'] = false;

}

}

}

return ans + 1;

}

---

이동할 때에는 0보다 크거나 같지만 배열의 길이보단 작아야합니다.

이 조건을 만족한다면, 해당 위치를 방문하였는지 체크해야합니다.

방문하지 않았다면, 방문하였다고 만든 다음에, 다시 재귀함수로 값을 호출합니다.

결국 얼마나 방문하였는지 체크하는 것이기 때문에 여기서는 ans이지만 본래 변수를 count로 잡는 것이 좋습니다.

재귀함수로 함수가 호출될 때 count는 하나씩 증가합니다. 

alphabet 함수에서 반환하는 값이 왜 ans+1인지 설명이 되는 부분입니다.

재귀함수로 호출한 다음에는 이동한 곳은 다시 방문하지 않았다고 해야 재귀함수로 다시 본 함수를

진행할 때 방문할 수 있으므로 Back Tracking을 진행합니다.

이 후에는 마찬가지로 ans (count) +1 로 반환하면 본 문제는 완성됩니다.

전체 코드는 다음과 같습니다. 

---

import java.util.Scanner;

public class 알파벳 {

public static final int[] dx = { 0, 0, 1, -1 };

public static final int[] dy = { 1, -1, 0, 0 };

private static Scanner scanner;

private static int alphabet(String[] board, boolean[] check, int x, int y) {

int ans = 0;

for (int i = 0; i < 4; i++) {

int nx = x + dx[i];

int ny = y + dy[i];

if ((nx >= 0 && nx < board.length) && (ny >= 0 && ny < board[0].length())) {

if (check[board[nx].charAt(ny) - 'A'] == false) {

check[board[nx].charAt(ny) - 'A'] = true;

int next = alphabet(board, check, nx, ny);

if (ans < next)

ans = next;

check[board[nx].charAt(ny) - 'A'] = false;

}

}

}

return ans + 1;

}

public static void main(String[] args) {

// TODO Auto-generated method stub

scanner = new Scanner(System.in);

int xNum = scanner.nextInt();

int yNum = scanner.nextInt();

scanner.nextLine();

String[] board = new String[xNum];

for (int i = 0; i < xNum; i++) {

board[i] = scanner.nextLine();

}

boolean check[] = new boolean[26]; // 알파벳 26개

check[board[0].charAt(0) - 'A'] = true; // 처음 시작 부분은 출발지점이기 때문에 이미 방문했다고 가정

int answer = alphabet(board, check, 0, 0);

System.out.println(answer);

}

}

---