
문제
세로 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; }
반응형
'알고리즘 > BOJ' 카테고리의 다른 글
[백준] 1806번: 부분합 (c++) (0) | 2021.09.15 |
---|---|
[백준] 13460번: 구슬 탈출2 (c++) (0) | 2021.09.13 |
[백준] 2263번: 트리의 순회 (c++) (0) | 2021.09.01 |
[백준] 12852번: 1로 만들기 2 (c++) (0) | 2021.08.30 |
[백준] 1005번: ACM Craft (c++) (0) | 2021.08.27 |