백준(BOJ) 1987번 알파벳
문제 : https://www.acmicpc.net/problem/1987
세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.
말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.
좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.
나의풀이:
기존 전형적인 DFS에 alphabet 배열을 매개 변수로 받아서 같은 알파벳이 나왔을 경우에는 가지 못하도록하는 조건을 추가해준다.
코드 ( C ++ )
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int R, C;
string map[20];
vector<char> v;
// 상하좌우를 위한 dy, dx 배열
int dy[4] = { 0,0,-1,1 };
int dx[4] = { 1,-1,0,0 };
int ret;
bool visited[20][20];
void go(int y, int x,bool alphabet[], int cnt)
{
for (int i = 0; i < 4; ++i)
{
int ny = y + dy[i];
int nx = x + dx[i];
if(ny >= 0 && ny < R && nx >= 0 && nx < C)
// 전형적인 dfs에 alphabet배열 조건만 추가 해준다.
if (!alphabet[map[ny][nx]-'A'] && !visited[ny][nx])
{
alphabet[map[ny][nx]-'A'] = true;
visited[ny][nx] = true;
go(ny, nx,alphabet, cnt + 1);
// 다음 반복문을 시작할때는 방금전 담았던 ny와 nx를 빼준다.
alphabet[map[ny][nx]-'A'] = false;
visited[ny][nx] = false;
}
}
// ret은 cnt가 가장 많이 나왔을때를 저장한다.
ret = max(ret, cnt);
}
int main()
{
cin >> R >> C;
for (int i = 0; i < R; ++i)
cin >> map[i];
// alphabet배열 0으로 초기화
bool alphabet[26] = { 0, };
// (0, 0) 구간에서 alphabet과 visited 방문 처리를 해주고 dfs 시작한다.
alphabet[map[0][0] - 'A'] = true;
visited[0][0] = true;
go(0, 0,alphabet, 1); // dfs 시작
cout << ret << endl;
return 0;
}
