알파벳

www.acmicpc.net/problem/1987

문제

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다.
보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데,
새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다.
즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오.
말이 지나는 칸은 좌측 상단의 칸도 포함된다.

입력

첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다.
(1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는
C개의 대문자 알파벳들이 빈칸 없이 주어진다.

출력

첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

예제 입력 1

2 4
CAAB
ADCB

예제 출력 1

3

예제 입력 2

3 6
HFDFFB
AJHGDH
DGAGEH

예제 출력 2

6

예제 입력 3

5 5
IEFCJ
FHFKC
FFALF
HFGCF
HMCHH

예제 출력 3

10

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2002 > 
Regional Competition – Juniors 3번

• 데이터를 추가한 사람: august14, doju, jh05013

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 깊이 우선 탐색
• 백트래킹

추가 반례

예제 입력 A

3 4

ABCD

BCDA

CDEF

예제 출력 3

3

예제 입력 B

10 10
ASWERHGCFH
QWERHDLKDG
ZKFOWOHKRK
SALTPWOKSS
BMDLKLKDKF
ALSKEMFLFQ
GMHMBPTIYU
DMNKJZKQLF
HKFKGLKEOL
OTOJKNKRMW

예제 출력 B

22

예제 입력 C

20 20
POIUYTREWQBWKALSLDLG
LKJHGFDSAMASFBMBOSOZ
NMBVCXZAKPAISJLBMROW
CEVTBFNIMLASNCVKNDKX
VPQLBKENMSAHBBLFOWPQ
ZLSKJJBNBEASZNFDGHHN
GPBMDLQDALAASBBXCEGA
APQIKBMROIBANPOBLMKS
ASKSKVJRPORHNOXZKSPN
LSNVOEOOOKAKANLGKOAX
AKVMBOTOWPQOJBSMSPEP
BLLBKWPEPBKNMROSALLP
BNQLDNBMKOVMEMELSLMA
RLEPQQPVKJRNBITNBSAS
ZXMCOITRPWKLPGKHNGMS
QOBKRPPPZSLEMPNKSPPR
OQJDNZNANDWKQKVJEOGJ
QUYVOIUYWERLKJHASDFV
ZCVWRETPOIUHJKLVBMAS
QWERZCVUIAFDKHSDFHSA

예제 출력 C

26

<틀린 코드>

오답이 나오는 반례는 없었으나… 계속되는 틀렸습니다…

포기하고 다르게 접근했다.

틀린 코드

#include <iostream>
#include <queue>
#include <string>
#include <set>

using namespace std;

#define MAX 21

int row, column, result;
char map[MAX][MAX];
bool mapcheck[MAX][MAX] = {false};
set<string> mySet;

struct Pos {
	// 나의 위치, 이동 횟수
	int posX, posY, trace;
	string strTrace;
} sPos;

// 나의 위치를 표현
queue<Pos> myQueue;

int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };

int main()
{
	for (int i = 0; i < MAX; i++)
	{
		for (int j = 0; j < MAX; j++)
		{
			map[i][j] = 'x';
		}
	}

	cin >> row >> column;
	for (int i = 1; i <= row; i++)
	{
		for (int j = 1; j <= column; j++)
		{
			char temp = ' ';
			cin >> temp;
			map[i][j] = temp;
		}
	}

	result = 0;
	sPos.posX = 1;
	sPos.posY = 1;
	sPos.trace = 0;
	sPos.strTrace = "";
	myQueue.push(sPos);

	while (!myQueue.empty())
	{
		Pos temp = myQueue.front();
		myQueue.pop();
		temp.strTrace.push_back(map[temp.posX][temp.posY]);
		temp.trace += 1;
		mapcheck[temp.posX][temp.posY] = true;
		
		if (result < temp.trace) result = temp.trace;
		if (mySet.count(temp.strTrace) != 0) continue;

		for (int i = 0; i < 4; i++)
		{
			int nx = temp.posX + dx[i];
			int ny = temp.posY + dy[i];

			if (mapcheck[nx][ny]) continue;
			if (nx <= 0 || nx > MAX || ny <= 0 || ny > MAX) continue;
			if (map[nx][ny] == 'x') continue;
			if (temp.strTrace.find(map[nx][ny]) != string::npos) continue;
			mySet.insert(temp.strTrace);

			Pos temp2 = temp;
			temp2.posX = nx;
			temp2.posY = ny;

			//cout << temp2.strTrace << "\n";
			myQueue.push(temp2);
		}
	}

	cout << result;
	return 0;
}

통과된 코드(DFS)

#include <iostream>

using namespace std;

// 행, 열, 결과
int row, column, result;

// 알파벳 중복 방지
bool isVisited[26];

// 맵 표시
char mapArr[20][20];

// 상 하 좌 우
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };

void DFS(int x, int y, int cnt) {

    // 결과값 보다 높으면 값을 바꾸어 준다.
    if (cnt > result)
    {
        result = cnt;
    }

    for (int i = 0;i < 4;i++)
    {
        // 상 하 좌 우 움직여주기
        int nx = x + dx[i];
        int ny = y + dy[i];

        // 범위를 벗어나면 실행 X
        if (nx >= 0 && ny >= 0 && nx < column && ny < row)
        {
            // A - 65  이번 배열에 A가 있다면 -65 = 0
            // isVisited[0] 방문 처리
            if (isVisited[mapArr[ny][nx] - 'A'] == false)
            {
                isVisited[mapArr[ny][nx] - 'A'] = true;
                DFS(nx, ny, cnt + 1);
                isVisited[mapArr[ny][nx] - 'A'] = false;
                // DFS가 끝나면서 방문 처리 해제
            }
        }
    }
}

int main() 
{
    cin >> row >> column;

    for (int i = 0;i < row;i++) 
    {
        for (int j = 0;j < column;j++) 
        {
            cin >> mapArr[i][j];
        }
    }

    // 첫시작
    isVisited[mapArr[0][0] - 'A'] = true;

    // DFS 시작
    DFS(0, 0, 1);

    cout << result;

    return 0;
}