BOJ 1987 알파벳

📎Problem Link

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

1987번: 알파벳

 

📋 문제 정리

• 세로 R X 가로 C 표 모양의 보드에 대문자 알파벳들이 적혀있음.
• 보드 판 위의 말은 좌측 상단 칸에 있음.
• 말이 존재한 위치에서 상하좌우로 인접한 네 칸중에 움직일 수 있는데, 이미 방문했던 알파벳이 적혀있는 칸으로는 움직일 수 없음.
• 좌측 상단에서 시작해서 말이 최대로 이동할 수 있는 칸 수를 구하기
• 첫째 줄에 R, C 입력 (1 ≤ R,C ≤ 20)
• 둘째 줄부터 R개의 줄에 보드의 대문자 알파벳 입력

📌 예제 1

예제1을 그림으로 나타내면 다음과 같다. 예제 1은 위와 같이 두가지 경우 밖에 없다. 그러므로 예제1의 결과 값은 3이 출력돼야한다.

 

📌 예제 2

 

예제2를 그림으로 나타내면 다음과 같다. 위의 그림은 시작점 H에서 움직일 수 있는 예시 중 일부이며, 최대로 움직일 수 있는 예시의 일부이기도 하다. 그러므로 예제 2에서는 6이 결과값으로 출력돼야한다.

 

📌 예제 3

예제3을 그림으로 나타내면 다음과 같다. 위의 예시의 결과 값을 미리 말하자면 10이다. 사실 위의 경우가 최대값을 구할 수 있는 유일한 예제인지 일부인지는 모르겠다. 위의 예시는 내가 유일하게 찾아낸 10을 만들어내는 경우이다. 

 

 

🧐 Idea

• 움직일때마다 지금까지 지나온 알파벳들과 겹치는지 확인해야 함. 배열 이용 or set 이용 중 고민함.
• count 변수는 지역변수로 하여 이전 칸으로 돌아갈 때 그 칸의 count값을 사용할 수 있게 함.

---

💻 Code

void DFS(int y, int x, int count) {
		count++;
		alpha[map[y][x] - 65] = 1;
		for (int i = 0; i < 4; i++) {

			int nx = x + mx[i];
			int ny = y + my[i];

			if (nx < 0 || nx >= C || ny < 0 || ny >= R) continue;

			if (!(alpha[map[ny][nx]-65]))
			{
				DFS(ny, nx, count);
			}
		}
		answer = max(answer, count);
		alpha[map[y][x] - 65] = 0;
	}

이번 문제는 DFS 함수를 눈여겨보자.  DFS를 실행하는 동시에 현재 위치에 대한 count++을 실행한다. int alpha[26]을 선언하여 각 알파벳에 대한 방문여부를 체크하도록 했다. 예를 들어, 현재 방문한 노드가 A이면 A에서 아스키 값 26을 뺀 0에 A에 대한 방문 여부가 입력된다. 

방문한 현재 노드에 대한 count와 알파벳을 체크한 후, 상하좌우의 알파벳을 방문한 적이 없을 경우에만 DFS를 실행하도록 했다.

좌측 상단에서부터 하나의 경로를 모두 돌았을 경우, max함수를 이용해서 최대 방문 수를 answer에 기록한다. 이전 경로들로 돌아가 다른 경로를 탐색할 때 방문하지 못하는 상황을 막기 위해 DFS를 나가기 직전에 현재 칸의 알파벳에 대한 방문 여부를 0으로 만든다.

---

사실 처음에 코드 작성을 했을 때는 set 선언 후, set에 알파벳을 넣으며 겹치는지 확인했다. 그러나 set 할당에서 시간을 꽤 할당하는지 시간초과가 났고, int형 배열로 바꿔 작성한 결과 "맞았습니다!!"를 볼 수 있었다:-)