알고리즘/BOJ

[백준] 1987번: 알파벳 (c++)

prefer2 2021. 8. 26. 11:04

 

문제


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

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

 

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

 

 

1987번: 알파벳

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

www.acmicpc.net

 

문제조건


  • 1 ≤ R,C ≤ 20
  • 말이 지나는 칸은 좌측 상단의 칸도 포함된다

 

풀이


문제에서 주어진 조건에 맞는 가능한 모든 경우들을 다 해보면 된다. DFS를 사용하여 백트래킹을 해주었다. 

대문자 알파벳으로 이루어진 보드이기 때문에 최대 26개까지 방문할 수 있다. 이를 쉽게 확인하기 위해 'A'를 빼주어서 방문 여부를 체크해 주었다(A는 0, B는 1, C는 2 ...)

 

코드


#include <iostream>
#include <vector>
using namespace std;
char board[21][21];
int r, c;
int mymax = 0;
bool visited[26];
void find(int x, int y, int cnt) {
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
if (cnt > mymax)mymax = cnt;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
//움직일 수 있는 위치라면 움직인다.
if (nx >= 0 && nx < r && ny >= 0 && ny < c) {
//이미 방문한 문자인지 확인
if (!visited[board[nx][ny] - 'A']) { //방문하지 않음
visited[board[nx][ny] - 'A'] = true;
find(nx, ny, cnt+1);
visited[board[nx][ny] - 'A'] = false;
}
}
}
}
int main() {
cin >> r >> c;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
cin >> board[i][j];
}
}
visited[board[0][0]-'A'] = true;
find(0, 0, 1);
cout << mymax;
}

 

 

 

반응형