[BOJ 백준] 1987 - 알파벳

 

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

1987번: 알파벳

백트래킹을 연습하기 위해 약 1달전, 2월 4일에 풀었을 때 틀렸던 문제를 다시 풀어보았다. 

 

그때 트렐로에 남겨둔 메시지는 이랬었다.

 

 

두가지 코드 모두 dfs의 기본적인 개념을 모르고 있어서 저러한 메시지를 남겼었고, 다른 사람의 코드를 봐도 이해하지 못했던 것이다.

 

한 달이 지난 지금, 다시 풀었을때 걸린시간은 딴 짓 포함 40분이었다. 그래도 이제는 백트래킹의 기본적인 문제를 풀 수 있게 된 것 같다. 물론 소스코드는 조금 비효율적으로 구현하였다.

 

 

사용된 변수, 함수는 다음과 같다

 

• 입력을 받는 map[][]
• 방문했던 알파벳인지를 확인해주기 한 alpha[]
• 해당 위치를 방문했음을 체크하는 visit[][]  --> 사실 이건 필요 없다. alpha로 충분히 체크 가능하다.
• 4방향 탐색을 위한 dy[] , dx[[]
• 백트래킹을 하기위한 dfs() 
  • dfs 함수의 파라미터에는 (y좌표, x좌표, 지나온 칸의 개수) 가 들어간다.
• 4방향 모두 전진을 하지 못하는 상황을 나타내는 flag 변수인 is_move 변수

 

구현한 로직은 다음과 같다

 

• 첫 칸도 지나온 칸에 포함해야하므로 dfs 시작전에 방문체크를 해준다.
• dfs 함수 내부에서 depth값과 result 값을 비교하여 최대값을 result 에 저장한다.
• 4방향 탐색을 하고 방문하지 않은 지점에서 depth 값을 1증가시켜 dfs 함수를 재귀호출한다.

 

굳이 visit 배열을 사용하지 않아도, alpha 배열 하나만으로 방문확인이 가능한데 중복으로 만들었다. 

탈출조건도 굳이 없어도 되는건데 is_move 라는 변수를 사용하여서 탈출할 수 있도록 하였다. 

 

 

 

소스코드

	#include<iostream>
	#include<algorithm>
	#define MAX 20
	using namespace std;
	char map[MAX][MAX];
	bool visit[MAX][MAX];
	bool alpha[26]; // 해당 알파벳이 쓰였는지
	int result = -1;
	int dy[4] = { 0,0,1,-1 };
	int dx[4] = { 1,-1,0,0 };
	int r, c;
	bool is_move = true;
	void dfs(int y, int x, int depth) {
	// 탈출조건이 : 더이상 전진할 곳이 없을 경우
	if (is_move == false) {
	cout << result << endl;
	return;
	}
	result = max(result, depth);
	char cur_alpha = map[y][x];
	int cur_idx = cur_alpha - 65;
	visit[y][x] = true;
	alpha[cur_idx] = true;
	for (int k = 0; k < 4; k++) {
	int ny = dy[k] + y;
	int nx = dx[k] + x;
	if (0 > ny || ny >= r || 0 > nx || nx >= c || visit[ny][nx] == true) continue;
	char next_alpha = map[ny][nx];
	int next_idx = next_alpha - 65;
	if (alpha[next_idx] == true) {
	is_move = false;
	continue;
	}
	is_move = true;
	visit[ny][nx] = true;
	alpha[next_idx] = true;
	dfs(ny, nx, depth + 1);
	visit[ny][nx] = false;
	alpha[next_idx] = false;
	}
	}
	int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> r >> c;
	string str;
	for (int i = 0; i < r; i++) {
	cin >> str;
	for (int j = 0; j < c; j++) {
	map[i][j] = str[j];
	}
	}
	dfs(0, 0, 1);
	cout << result;
	}

view raw 알파벳.cpp hosted with ❤ by GitHub

 

 

 

좀 더 깔끔한 소스코드

 

	#include<iostream>
	#include<algorithm>
	#define MAX 20
	using namespace std;
	char map[MAX][MAX];
	bool alpha[26]; // 해당 알파벳이 쓰였는지
	int result = -1;
	int dy[4] = { 0,0,1,-1 };
	int dx[4] = { 1,-1,0,0 };
	int r, c;
	bool is_move=true;
	void dfs(int y, int x, int depth) {
	result = max(result, depth);
	for (int k = 0; k < 4; k++) {
	int ny = dy[k] + y;
	int nx = dx[k] + x;
	if (0 > ny || ny >= r || 0 > nx || nx >= c) continue;
	char next_alpha = map[ny][nx];
	int next_idx = next_alpha - 65;
	if (alpha[next_idx]==true) {
	continue;
	}
	alpha[next_idx] = true;
	dfs(ny, nx, depth + 1);
	alpha[next_idx] = false;
	}
	}
	int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> r >> c;
	string str;
	for (int i = 0; i < r; i++) {
	cin >> str;
	for (int j = 0; j < c; j++) {
	map[i][j] = str[j];
	}
	}
	alpha[map[0][0] - 65] = true; // 시작지점은 방문처리
	dfs(0, 0, 1);
	cout << result;
	}

view raw 알파벳(수정).cpp hosted with ❤ by GitHub