[코딩테스트]백준 - 알파벳

알파벳

문제

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

입력

첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

출력

첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

예제 입력 1

2 4
CAAB
ADCB

예제 출력 1

3

출처

• Olympiad > Croatian Highschool Competitions in Informatics > 2002 > Regional Competition - Juniors 3번
• 데이터를 추가한 사람: august14 doju jh05013

링크

PKU Judge Online

알고리즘 분류

• DFS
• 백트래킹

해결한 코드

var fs = require('fs');
var input = fs.readFileSync('/dev/stdin').toString().split('\n');
// var input = fs.readFileSync(__dirname + '/stdin.txt').toString().replace(/\r/g, "").split('\n');
var number = input[0].split(' ')
var r = parseInt(number[0])
var c = parseInt(number[1])
var array = new Array(input.length - 1)
// 알파벳 문자열을 2차원 행렬 모양처럼 2차원 배열로 만들어주기 위한 배열 
for (var i = 1; i < input.length; i++) {
    var ptr = input[i].split('')
    array[i - 1] = ptr
}
var visit = new Array(26).fill(false)

var dx = [1, -1, 0, 0]
var dy = [0, 0, 1, -1]

function code(str){
  return str.charCodeAt(0)
}

function backtrack(x, y){
  var answer = 1
  // array[0][0]부터 시작하니까 최소 칸수는 1
  for(var i=0; i<4; i++){
    var nx = x+dx[i]
    var ny = y+dy[i]
    if((nx >= 0 && nx < r) && (ny >= 0 && ny < c)){
      if(!visit[code(array[nx][ny]) - code('A')]){
        visit[code(array[nx][ny]) - code('A')] = true
        answer = Math.max(answer, backtrack(nx, ny) + 1)
        // 최대 칸 수를 구하는 것이니까 둘 중 더 큰값을 answer로 지정 
        // backtrack 함수로 한번 더 간다 => 다음 알파벳 칸으로 이동한다는 것이니까 +1 해줌
        visit[code(array[nx][ny]) - code('A')] = false
        // backtrack에서 칸 이동 하지 못하고 되돌아오면 true를 false로 되돌리기 
      }
    }
  }
  return answer
}
visit[code(array[0][0]) - code('A')] = true
// array[0][0]에서 시작하니까 방문 기록 해주기
console.log(backtrack(0, 0))

알고리즘

1. 가장 먼저, 문제를 풀 수 있게 필요한 변수들을 만들어놓는다.

• 이동할 문자열의 행 길이 = r
• 이동할 문자열의 열 길이 = c
• 이동할 문자열을 2차원 배열(array)로 만들기

[ 
  [ 'C', 'A', 'A', 'B' ], 
  [ 'A', 'D', 'C', 'B' ] 
]

• 알파벳 방문여부를 기록할 visit 배열 만들기
  ※ 알파벳은 26개이므로 26칸짜리 배열을 만든다.

[ false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false ]

• array 좌표 내 x, y를 상하좌우로 움직일 수 있도록 하는 dx, dy를 만든다.

var dx = [1, -1, 0, 0]
var dy = [0, 0, 1, -1]

2. array[0][0]부터 상하좌우로 탐색하면서 방문하지 않은 알파벳의 갯수를 세어준다.

2-1. 우선 array[0][0]부터 시작하니까 무조건 1칸은 방문한다.
2-2. 현재의 위치인 array[x][y]에서 상하좌우로 탐색한다.
※ array 내 x, y가 상하좌우로 움직이며 탐색할 수 있는 범위는 0 ≤ x ≤ r, 0 ≤ y ≤ c이므로, 0 ≤ x + dx[i] ≤ r, 0 ≤ y + dy[i] ≤ c가 만족할 때, 해당 위치의 알파벳이 방문한 알파벳인지 아닌지 확인한다.
📍 어떻게 확인하지? 아스키코드를 활용했다.
👉🏻 예를 들어, 해당 위치의 알파벳이 만약 A라면,
A의 아스키코드 값 - 'A'의 아스키코드 값 = 0
따라서, visit[0]이 false인지 확인한다.
(만약 false라면) visit[0]의 값을 true로 바꿔준 후, 다음 알파벳을 탐색하기 위해 재귀로 함수를 부른다.
👉🏻 해당 위치의 알파벳이 만약 D라면, D의 아스키코드 값 - 'A'의 아스키코드 값 = 3
(만약 false라면) visit[3]의 값을 true로 바꿔주고 다음 알파벳 탐색을 위해 재귀 함수를 부른다.

3. 최대 칸수를 구하는 것이니까, 현재 이동한 칸 수 vs 이전에 이동한 칸 수 중 더 큰값을 답으로 한다.

이렇게 풀었더니 해결되었다.
원래는 visit배열로 방문 기록을 하는 방법이 아니라 다른 방법으로 구했었다.

이전 방법 코드

function b1987() {
    var fs = require('fs');
    var input = fs.readFileSync('/dev/stdin').toString().split('\n');
    // var input = fs.readFileSync(__dirname + '/stdin.txt').toString().replace(/\r/g, "").split('\n');
    var number = input[0].split(' ')

    var r = parseInt(number[0])
    var c = parseInt(number[1])

    var array = new Array(input.length-1)
    for (var i = 1; i < input.length; i++) {
        var ptr = input[i].split('')
        array[i-1] = ptr
    }
    var ans = [array[0][0]]
    // array[0][0]은 무조건 방문하니까 ans에 넣고 시작한다. 
    var result = ['0']
    backtrack(r, c, array, 0, 0, ans, result)
    console.log(result[0].length)
  // result[0]의 길이를 출력 
 
}

function backtrack(r, c, array, x, y, ans, result) {
    var flag = false
    var tempAns = ans.slice()
    // tempAns = ans배열을 복사한 배열 
    var dx = [1, -1, 0, 0]
    var dy = [0, 0, 1, -1]
    for (var i = 0; i < 4; i++) {
        if ((x + dx[i] >= 0 && x + dx[i] < r) && (y + dy[i] >= 0 && y + dy[i] < c)) {
            if (!tempAns.includes(array[x + dx[i]][y + dy[i]])) {
              // 만약 현재 알파벳이 tempAns에 없으면 
                tempAns.push(array[x + dx[i]][y + dy[i]])
              // tempAns에 해당 알파벳을 넣음
                flag = true
              // 이 과정을 거치면 flag = true, 거치지 않으면 false
                backtrack(r, c, array, x + dx[i], y + dy[i], tempAns, result)
                tempAns.pop()
            }
        }
    }
    if (flag == false) {
        // 만약 위 과정을 거치지 않았으면 
        if(result.length === 0){
            result[0] = tempAns
        } else if(tempAns.length > result[0].length){
          // tempAns의 길이가 result[0]의 길이보다 길때에만 
            result[0] = tempAns
          // result[0]을 바꿔줌 
          // result[0]에 길이가 가장 긴 배열만 들어가게 함 
        }
        return
    }
}
b1987()

질문하기에 올라온 반례도 모두 잘 계산되었고, 시간도 그렇게 오래 걸리지 않은 것 같은데(?) 채점하면 시간초과였다.
아무래도 visit의 방문 기록을 보는 것보다 include를 사용하는데 시간이 더 많이 소요되었고,
또 result라는 배열에 담아서 출력하는 것보다 단순히 이동한 칸 수를 +1 해주는게 더 빠르기 때문에 이 코드는 틀렸던 게 아닐까.. 짐작해본다.