백준 1987 - 알파벳

문제 링크입니다 https://www.acmicpc.net/problem/1987

1987번: 알파벳

깊이 우선 탐색(BFS) 문제였습니다.

문제 조건입니다.

한번 지나간 알파벳은 지나가지 않고 최대로 갈 수 있는 횟수를 구하는 문제입니다.

 

예를 들어 

CAAB

ADCB     의 경우에는 C -> A -> D 총 3번이 됩니다.

 

접근 방법

1. 26칸을 가진 배열을 선언해 이동중에 어떤 알파벳이 입력되었는지 저장한다.

2. 상, 하, 좌, 우를 확인하여 갈 수 있는 경로를 확인한다.

3. 갈 수 있는 경로를 찾은 경우, 이동 경로+1을 한뒤 해당 칸으로 움직인다.

4. 갈 수 있는 곳까지 갔다면, 돌아오면서 마지막에 갔던 알파벳을 0으로 만들어 다른 경우에도 확인할 수 있도록 한다.

5. DFS의 모든 과정에서 이동 경로의 최댓값을 계속 비교한다.

 

map[xx][yy] - 'A' -> 이 방법을 통해서 이동했던 알파벳들을 알아낼 수 있습니다. map 배열도 char형임으로 'A'를 뺀다면 몇번째 알파벳을 들렸는지 값을 얻을 수 있습니다(A == 0, B == 1,.....) 자세한 것은 아스키코드를 참고해주세요!

 

자세한 것은 코드를 참고해주세요

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#include <stack>
using namespace std;

int R, C;
char map[21][21];
int arr[4] = { 0,1,0,-1 };
int arr2[4] = { 1,0,-1,0 };
int check[26];
int ans;

void dfs(int x, int y, int z) {
    ans = max(ans, z);
    for (int i = 0; i < 4; i++) {
        int xx = x + arr[i];
        int yy = y + arr2[i];
        if (xx >= 1 && yy >= 1 && xx <= R && yy <= C) {
            if (check[map[xx][yy] - 'A'] == 0) {
                check[map[xx][yy] - 'A'] = 1;
                dfs(xx, yy, z + 1);
                check[map[xx][yy] - 'A'] = 0;
            }
        }
    }
}

void solve() {
    check[map[1][1] - 'A'] = 1;
    dfs(1, 1, 1);
    cout << ans;
}

int main() {
    cin.tie(0);
    cout.tie(0);
    cin >> R >> C;
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            cin >> map[i][j];
        }
    }
    solve();
    return 0;
}

 

 

질문 및 조언 댓글 남겨주세요!