[BOJ/C++] 1987 알파벳

문제 링크 https://www.acmicpc.net/problem/1987

📝 문제

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

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

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

💻 코드

#include <iostream>
#include <algorithm>
using namespace std;

int N, M;
char arr[21][21];
int visited[26];

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

int result = 0;

void dfs(int x, int y, int cnt)
{
	result = max(result, cnt);

	for (int k = 0; k < 4; k++) {
		int nx, ny;
		nx = x + dx[k];
		ny = y + dy[k];

		if (nx < 0 || ny < 0 || nx >= N || ny >= M ) continue;

		int next = (int)arr[nx][ny] - 65;

		if (visited[next] == 0)
		{
			visited[next] = 1;
			dfs(nx, ny, cnt + 1);
			visited[next] = 0;
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> arr[i][j];
		}
	}

	int start = (int)arr[0][0] - 65;
	visited[start] = 1;
	dfs(0, 0, 1);

	cout << result;
}

📌 해결방법

1. DFS와 방문 체크를 사용하여 문제풀기!
2. visited[26]으로 알파벳 개수만큼 설정하여 방문체크 해주기

💡 배운 점

- char 배열

• int arr[][]을 사용하는 것 처럼 char arr[][]을 사용한다면
  문자열 한글자씩 저장 가능!

cin >> N >> M;
for (int i = 0; i < N; i++) {
	for (int j = 0; j < M; j++) {
		cin >> arr[i][j];
	}
}

• 이런 식으로 사용하면 arr[i][j]에 알파벳 한 글자씩 들어온당

- (int)arr[0][0] - 65;

• 아스키코드를 이용한 형변환 방법
• 'A' = 65, 'a' = 97 기억해두기
• 'A'의 경우 int로 형변환 후 -65 를 하면 0
  → visited[0]을 'A'로 설정
• 'Z'의 경우 int로 형변환 후 -65 를 하면 25
  → visited[25]을 'Z'로 설정

int temp = (int)arr[0][0] - 65
visited[temp] = 1  // 방문체크 해주기!

---

✔ 느낀 점

문자열이 나왔길래 이거는 대체 어떻게 저장해야되지 하다가 char로 해서 저장했더니 바로 저장이 됐다,,,, 짱
원래는 vector로 내가 방문하는 알파벳들을 추가한 뒤에 in vector 같은 방법을 사용해서 구하려고 했었는데... 파이썬과 달리 in 이 안되는 것 같았다. 그래서 방문체크를 사용하는 방법으로 변경 완.