백준 1987번 알파벳 (C++)

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

1987번: 알파벳

문제 요약

 

1. r*c 크기의 2차원 배열에는 알파벳 대문자들이 적혀있습니다.

2. 시작지점은 배열의 좌측 맨 위쪽이며, 한번의 이동으로 왼쪽, 오른쪽, 위, 아래를 갈 수 있습니다.

3. 같은 알파벳은 두번 이상 지나갈 수 없습니다.

4. 최대한으로 많이 지나갈 수 있는 알파벳의 갯수를 출력하세요. 시작지점인 좌측 맨 위쪽도 지나간 칸에 포함됩니다.

 

핵심 포인트

 

전형적인 백트래킹 문제입니다. 백트래킹 원리만 잘 알고있으면 쉽게 풀 수 있습니다.

 

문제 풀이

 

1. 전역변수로 필요한 변수들을 선언합니다.

int r, c, mx[]={1,-1,0,0}, my[]={0,0,1,-1}, ans = 0;
char v[20][20]; // 문자배열 r*c
bool abc[26]; // A~Z까지 방문 여부

 

2. 배열을 입력받고 배열의 [0][0] 지점은 방문 표시를 해줍니다.

    cin >> r >> c;
    for(int i=0; i<r; i++){
        for(int j=0; j<c; j++) cin >> v[i][j];
    }
    abc[v[0][0]-'A'] = true;
    move(0,0,1);
    cout << ans << "\n";

그리고 move함수를 구현하여 정답을 구합니다.

move함수의 인자는 각각 y좌표,x좌표,누적 움직임 횟수 입니다.

 

3. 다음은 move함수의 내부입니다.

void move(int y, int x, int cnt){
    if(cnt>ans) ans = cnt; // 1
    for(int i=0; i<4; i++){ // 2
        int ny = y+my[i]; // 3
        int nx = x+mx[i];
        if(ny<0||ny>=r||nx<0||nx>=c||abc[v[ny][nx]-'A']) continue; // 4
        abc[v[ny][nx]-'A'] = true; // 5 
        move(ny,nx,cnt+1); // 6 
        abc[v[ny][nx]-'A'] = false; // 7
    }
}

(1) 만약 cnt가 ans보다 크다면 ans를 새로 갱신합니다.

(2) 4방위로 for문을 돌립니다.

(3) ny와 nx는 새로운 위치입니다. 이 두 변수는 전역변수가 아닌 지역변수로 선언되어야 합니다.

(4) 만약 새로운 위치가 배열의 범위를 벗어났거나, 새로운 위치의 알파벳이 이미 사용된 알파벳이라면 continue를 합니다.

(5) 새로운 위치의 알파벳에 방문체크를 합니다.

(6) 새로운 위치를 기반으로 다시 move함수를 호출합니다.

(7) 새로운 위치의 알파벳에 방문체크를 해제합니다.

 

4. move함수가 종료된 뒤 정답을 출력합니다.

 

#include <iostream>
#include <algorithm>
using namespace std;

int r, c, mx[]={1,-1,0,0}, my[]={0,0,1,-1}, ans = 0;
char v[20][20];
bool abc[26];

void move(int y, int x, int cnt){
    if(cnt>ans) ans = cnt;
    for(int i=0; i<4; i++){
        int ny = y+my[i];
        int nx = x+mx[i];
        if(ny<0||ny>=r||nx<0||nx>=c||abc[v[ny][nx]-'A']) continue;
        abc[v[ny][nx]-'A'] = true;
        move(ny,nx,cnt+1);
        abc[v[ny][nx]-'A'] = false;
    }
}

int main() {
    ios_base::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 >> v[i][j];
    }
    abc[v[0][0]-'A'] = true;
    move(0,0,1);
    cout << ans << "\n";
    return 0;
}