[BOJ] 백준 1987번 알파벳 c++

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

1987번: 알파벳

R * C 크기의 표 모양의 보드가 알파벳으로 이뤄진채 주어진다.

말은 보드의 좌측 상단에서 시작해 상하좌우 4방향으로 한 칸씩 이동 가능하다.

단, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과 달라야한다.

이때 말이 최대한 몇칸을 지날 수 있는지 구하는것이 문제이다.

 

해당 문제는 dfs를 이용하여 문제를 풀 수 있다.

여기서 중요한점은 이미 지나온 경로에 있는 알파벳을 따로 저장하여 앞으로의 경로와 비교해야 한다는 것이다.

나는 지나온 알파벳을 비트마스크 형태로 저장하여 다음 경로의 알파벳과 bit단위 비교를 하여 다음 경로가 유효한지 판단하였다.

	#include<iostream>
	using namespace std;
	char map[20][20];
	int dx[4] = {0, 0, -1, 1};
	int dy[4] = {-1, 1, 0, 0};
	int R, C;
	// 인자로 넘어온 알파벳의 비트마스크 표현 return
	int charTobit(char c) {
	int x = c - 'A';
	return (1 << x);
	}
	// 맵 범위 검사
	bool boundValidation(int x, int y) {
	if (x < 0 || x >= C)
	return false;
	if (y < 0 || y >= R)
	return false;
	return true;
	}
	// 지나온 알파벳중에 있는지 비트마스크를 이용한 검사
	bool alreadyHave(char c, int state) {
	int next = charTobit(c);
	if ((state & next) > 0)
	return true;
	return false;
	}
	// dfs를 이용
	int tracking(int state, int curX, int curY) {
	int ret = 1;
	for (int i = 0; i < 4; i++) {
	int nextX = curX + dx[i];
	int nextY = curY + dy[i];
	// 다음 이동지역이 범위를 벗어나거나 지나온 알파벳중에 있으면 무시
	if (boundValidation(nextX, nextY)&&!alreadyHave(map[nextY][nextX],state)) {
	// 다음 지역의 알파벳을 상태에 넣고 다음상태로 재귀
	int nextState = state | charTobit(map[nextY][nextX]);
	ret = max(ret, tracking(nextState, nextX, nextY) + 1);
	}
	}
	return ret;
	}
	int main() {
	cin >> R >> C;
	for (int i = 0; i < R; i++)
	for (int j = 0; j < C; j++)
	cin >> map[i][j];
	cout << tracking(charTobit(map[0][0]), 0, 0);
	}

view raw [BOJ] 백준 1987번 알파벳.cpp hosted with ❤ by GitHub

코드 원본 : https://github.com/sbl133/BOJ/blob/main/%231987.cpp

GitHub - sbl133/BOJ

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!