[백준]1987번 알파벳 - C/C++

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

1987번: 알파벳

문제

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

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

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

입력

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

출력

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

---

간단하게 DFS 로 풀 수 있는 문제이다.

같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 알파벳은 총 26개 이므로 int 형의 vis 변수 하나를 둔다면 비트 마스킹으로 쉽게 백트래킹을 할 수 있다.

#include <iostream>

using namespace std;

int R, C;
char arr[22][22];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,-1,0,1 };
int res = 0;

void solve(int y, int x,int cnt,int vis) {
	int newX, newY;
	if (res < cnt) 
		res = cnt;
	int tmp = arr[y][x] - 'A' ;
	vis = vis | (1 << tmp);
	for (int i = 0; i < 4; i++) {
		newX = x + dx[i];
		newY = y + dy[i];
		if (newX > 0 && newX <= C && newY > 0 && newY <= R) {
			int c = arr[newY][newX] - 'A' ;
			if(!(vis&(1<<c)))
				solve(newY, newX, cnt + 1,vis);
		}
	}

}


int main() {
	cin >> R >> C;

	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			cin >> arr[i][j];
		}
	}

	solve(1, 1, 1,0);
	cout << res;
	return 0;
}

---

저번 주말부터 아파가지고 공부를 하나도 하지 못했다. 4일 연속으로 쉰 게 얼마만인지 모르겠는데 군대 가기 전 휴학했을 때 생각도 나고 정말 행복했다. 많은 사람들이 격리를 할 때 답답하다고 하는데 나는 푹 쉴 수 있어서 정말 좋았다. 4일을 공부를 하지 않고 쭉 쉬니깐 다시 공부를 시작하는 것이 쉽지 않았다. 하지만 다시 시작한 김에 또 열심히 해야겠다!

 

삼성 알고리즘 특강 문제는 규모가 커서 굉장히 오래걸린다. 오늘 내로 풀지 못할 것 같아 백준 문제나 풀어보려고 골드 4 문제 중 사람들이 제일 많이 푼 문제를 건드렸다. 정답률이 20% 대여서 조금은 어려울 줄 알았는데 막힘없이 쭉쭉 풀었고 컴파일을 하자마자 예제도 다 맞고 '맞았습니다'까지 띄웠다. SWEA 특강을 들으면서 어렵다는 생각이 많이 들어서 실력에 의구심이 들 때가 많이 있었는데 그래도 실력이 조금은 는 것 같다!