[백준 알고리즘][백트래킹] 1987번 알파벳

문제

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

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

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

문제 출처: 백준 온라인 저지(https://www.acmicpc.net/problem/1987)

 

입력과 출력

첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1<=R,C<=20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다. 출력은 말이 지날 수 있는 최대의 칸 수를 출력한다.

 

풀이

앞에 풀었던 N-Queen문제랑 비슷한 것 같다. 이문제에서는 N*N 체스판 대신에 R*C의 보드가 주어진다. 그리고 앞에 문제에서는 promising 이 같은 가로줄, 세로줄, 가로줄의차이와 세로줄의 차이가 같지않고 달라야했는데 이 문제에서는 지금까지 밟지 않았던 알파벳이어야한다. R*C 칸의 보드를 모두 밟아보며 다 시도를 해봐야하지만 만약 밟았던 곳이 나오면 지나가지못하고 다시 돌아가야한다. 그리고 만약 앞으로 나아갈 곳이 없어서 돌아가야한다면 부분집합의 합문제를 풀 때 sum을 다시 마이너스 해준 것 처럼 사용한 알파벳이 아니도록 used에 대한 유무를 표시해줘야한다. 최대의 칸 수를 출력해야하므로 만약 앞으로 나아가지 못하는 순간이 되면 그 때의 값이 max이 될 때 값을 계속해서 저장해두고 비교해서 하나의 변수로 사용하면 될 것 같다.

테스트케이스 여러개 돌려서 다 맞았는데 9%에서 틀렸습니다가 나온다.(바보같이 알파벳 배열 사이즈를 25로해서 틀렸었다.)

+추가 2019.01.04

채점이 런타임 에러가 되어있어서 새로 풀었는데 void main을 써서였고 이 때 풀었던 방식이랑 똑같이 풀었다. 새로 푼 코드가 조금 더 깔끔해보이긴 하지만 비슷한 것 같다.

코드

void backtrack(int x, int y)

{

int check = board[x][y]-'A';

int i;

if(used[check] == 0) // 이자리가 사용할 수 없다면

{

max = max(max, cnt);

return ; //돌아가서 종료되도록 -> 이때까지의 가장 긴 스탭을 계산해둔다

}

used[check] = 0;

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

{

if( x+dx[i] < 0 || y+dy[i] < 0 || x+dx[i] >= R || y+dy[i] >= C) 

continue; 

cnt++;

backtrack( x+dx[i], y+dy[i]);

cnt--;

}

used[check] = 1; //더이상 갈데가 없어서 끝났다면 안사용한걸로

}

new 버전: https://github.com/kswim/Algorithm/blob/master/Backtracking/1987.cpp