백준 1987번 (알파벳, C++, DFS) / 추가 반례 [BAEKJOON]

2 4
CAAB
ADCB

3

3 6
HFDFFB
AJHGDH
DGAGEH

6

5 5
IEFCJ
FHFKC
FFALF
HFGCF
HMCHH

10

3 4

ABCD

BCDA

CDEF

3

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

22

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

26

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

#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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

#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;
}