백준 1987번 - 알파벳 C++ 풀이

문제 풀이 시간 : 1시간

문제 요약

보드의 각 칸에는 알파벳이 있음
주변의 네 칸 중 다른 칸으로 이동한다.
새로 이동한 칸은 지금까지 지나온 알파벳이 아니어야 함.
최대로 갈 수 있는 칸 수 구하기

문제 풀이

이 문제는 간단하게 DFS로 풀 수 있겠다고 생각했다.

초기 코드

c++

#include <iostream>
#include <vector>
#include <string>

using namespace std;

char board[21][21];
int arr[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
int r, c, ans;

bool check(int x, int y) { //보드를 넘어가는지 확인
    if ((x >= 0 && x < r) && (y >= 0 && y < c))
        return true;
    else
        return false;
}

void find(bool visited[21], int x, int y, int sum) { //DFS함수
    int tx, ty;
    ans = max(sum, ans); //현재 값이 최댓값보다 크면 교체
		visited[board[x][y] - 'A'] = true; //방문 처리
    for (int i = 0; i < 4; i++) { //주변 칸 탐색
        tx = x + arr[i][0]; 
        ty = y + arr[i][1];

        if (check(tx, ty)) { //보드를 넘어가지 않으면
            if (!visited[board[tx][ty] - 'A']) { //방문되지 않았다면
                find(visited, tx, ty, sum + 1); 
            }
        }
    }
}

int main() {
    string input;
    cin >> r >> c;
    for (int i = 0; i < r; i++) {
        cin >> input;
        for (int j = 0; j < c; j++)
            board[i][j] = input[j];
    }
    bool visited[21] = {false};
    visited[board[0][0] - 'A'] = true;
    find(visited, 0, 0, 1);
    cout << ans;
}

위 코드는 아쉽게도 바로 틀렸다고 한다.

이유가 무엇일까?

이유는 이미 방문 했더라도 다른 경우가 있을 수 있기 때문에 방문 후 다시 방문하지 않았다고 해주어야 한다.

아래와 같은 경우를 보자.

(0,0)에서 시작하므로 갈 수 있는 칸은 (1,0)과 (0,1)이다.

이때 만약 (1,0)으로 간다면 (2,0)과 (1,1) 모두 이미 방문한 것이므로 이동 횟수는 2이다.

하지만 (0,0)에서 (0,1)로 이동한다면 아래와 같이 4가 나온다.

따라서 다른 칸으로 방문한 후 visited를 다시 false로 바꿔주어 주변의 다른 칸에 같은 알파벳이 있어도 방문할 수 있도록 해주어야한다.

최종 코드

c++

#include <iostream>
#include <algorithm>

using namespace std;

char board[21][21];
int arr[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
int r, c, ans;

bool check(int x, int y) { //보드를 넘어가는지 확인
    if (x >= 0 && x < r && y >= 0 && y < c)
        return true;
    else
        return false;
}

void find(bool visited[27], int x, int y, int sum) { //DFS함수
    int tx, ty;
    if (ans < sum) //현재값이 최댓값보다 크면 교체
        ans = sum;
    for (int i = 0; i < 4; i++) { //주변 칸 탐색
        tx = x + arr[i][0];
        ty = y + arr[i][1];

        if (check(tx, ty)) { //보드를 넘어가지 않고
            if (!visited[board[tx][ty] - 'A']) { //방문하지 않았다면
                visited[board[tx][ty] - 'A'] = true; //방문 처리
                find(visited, tx, ty, sum + 1); //DFS 호출
                visited[board[tx][ty] - 'A'] = false; //방문 취소
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> r >> c;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++)
            cin >> board[i][j];
    }
    bool visited[27] = {false};
    visited[board[0][0] - 'A'] = true;
    find(visited, 0, 0, 1);
    cout << ans;
}

1987번 - 알파벳

문제 풀이 시간 : 1시간

문제 요약

문제 풀이

초기 코드

최종 코드

함께 읽으면 좋은 글

2186번 - 문자판

11657번 - 타임머신

16234번 - 인구 이동

2096번 - 내려가기