1987 - 알파벳

문제

코드

#include<bits/stdc++.h>
using namespace std;

int r,c,ma,ret;
pair<int,int> p;
queue<pair<int,int>> q;
int visited[30];
char a[30][30];
const int dy[4] = {-1,0,1,0};
const int dx[4] = {0,1,0,-1};


void solve(int y, int x, int cnt){
	ret = max(ret, cnt);
	for(int i = 0; i < 4; i++){
		int ny = y + dy[i];
		int nx = x + dx[i];
		if(ny< 0 || ny >= r || nx < 0 || nx >= c) continue;
		int next = (int)(a[ny][nx] - 'A');
		
		if(visited[next] == 0){
			visited[next] = 1;
			solve(ny,nx,cnt+1);
			visited[next] = 0;
		}
	}
}


int main(){
	cin >> r >> c;
	
	for(int i = 0; i < r; i++){
		for(int j = 0; j < c; j++){
			cin >> a[i][j];
		}
	}
	visited[(int)a[0][0] - 'A'] = 1;	
	solve(0,0,1);
	cout << ret << '\n';
}

풀이

완전탐색 하는 기본적인 문제였다.
전부 대문자라는 조건이 있었기에 visited 배열에 넣기 전에 -'A'를 해주어 'A'를 0으로 기준점을 잡아줬다.
solve 함수는 y,x좌표 이외에도 cnt를 넣었는데 이게 최대값을 구해주는데 사용된다. 한 칸에서 상,하,좌,우를 탐색하고 겹치는 알파벳이면 가지 않고 cnt를 하나 올리고 또 탐색을 한다. 근데 탐색을 하도록 하고 방문했다는 정보를 0으로 바꿔줘야 한다.
a - b (1을 막대기라 생각하고) a에서 오른쪽 b로 가고 b를 solve함수에 넣는다.
1 하지만 그렇게 되면 a 아래 있는 b를 탐색하지 않기
b 때문에 visited[a]를 0으로 초기화 해줘야하는 것이다. 이렇게 전체를 탐색하면 어렵지 않게 해결할 수 있다.

결과

후기

완전탐색이라는 기본 아이디어는 알고 있었으나 세부적인 로직을 짜는데서 어려움을 살짝 겪었다. cnt를 어떻게 올리고 어떻게 비교할지에 대한 아이디어에서 어려움을 겪은 듯 하다.