[BOJ 1987] 알파벳

문제 출처

https://www.acmicpc.net/problem/1987

dfs로 순회해주면 된다.

bitmask 대신 visit을 사용해도 되지만 오늘 bitmask를 공부한 관계로 bitmask를 사용해 보았다.

문제자체는 단순 순회니 어렵지 않은 문제

소스코드

//
//  main.cpp
//  BOJ_1987
//
//  Created by sw on 05/01/2019.
//  Copyright © 2019 sw. All rights reserved.
//
#include<iostream>
#include<algorithm>
using namespace std;
int r, c;
char map[21][21];
 
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };
 
int dfs(int x, int y, int status) {
    int ret = 1;
    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        if (nx < 0 || ny < 0 || nx >= r || ny >= c)
            continue;
        
        int v = 1 << (map[nx][ny] - 'A');
        if (status & v)
            continue;
        
        ret = max(ret, dfs(nx, ny, status | v) + 1);
    }
    return ret;
}
 
int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> r >> c;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cin >> map[i][j];
        }
    }
    cout << dfs(0, 0, 1 << (map[0][0] - 'A'));
    return 0;
}