백준(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;

}