[백준 BOJ][C++]1987번 알파벳 풀이: DFS/BFS

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

1987번: 알파벳

 

 이 문제는 DFS를 사용하여 해결할 수 있습니다. 

 

 이 문제의 답은 DFS를 했을 때 리프 노드의 부모 노드의 개수 + 1의 최댓값이 됩니다. 

 

문제에 주어진 예시를 한 번 보겠습니다. 

 

 2  4

 C A A B

 A D C B                         

index: x(col), y(row)	0	1	2	3
0	C	A	A	B
1	A	D	C	B

 

이 정보를 가지고 DFS를 진행하게 되면 다음과 같이 됩니다. 

 

 DFS의 특성 상 한 쪽 방향으로의 경로를 모두 탐색 후 다음 경로를 탐색하게 됩니다.

 

 이때 리프 노드의 부모 노드 개수 + 1이 해당 경로의 길이가 됩니다. 

 

 이것을 이해하셨다면 코드는 쉽게 이해하실 수 있습니다!

 

char alpha[21][21];  //알파벳 맵
int r, c; //행, 열 수
int maxnum = 0;  //최대 길이

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

typedef struct node {
	int x, y;  //위치
	int parent_num;  //부모 노드 개수
	int alpha_visit[26] = { 0, };  //지나온 알파벳
}node;

 alpha[][]는 r*c 배열의 알파벳 정보를 기록할 2차원 배열입니다. 

 

 r과 c는 높이와 너비를 나타내며 maxnum은 말이 지나갈 수 있는 최대 칸 수를 의미합니다. 

 

 dx[]와 dy[]는 이동 가능한 위치 변화량을 의미합니다. (동, 서, 남, 북)

 

 node 구조체는 각 위치에 해당하는 알파벳의 정보를 나타냅니다. 

 

 x, y: 해당 노드의 alpha[][]내에서의 위치 (x, y)

 parent_num: 해당 노드의 부모 노드의 개수

 alpha_visit[]: 루트 노드부터 해당 노드까지 지나온 알파벳의 정보(지났으면 1, 지나지 않았으면 0)

                 (index 0~25: 차례대로 A~Z)

 

void dfs() {

	int flag;
	int tx, ty;
	stack<node> s;
    
	node temp;  //시작 노드, 좌측 상단에 있는 노드
	temp.x = temp.y = temp.parent_num = 0;
	temp.alpha_visit[alpha[0][0] - 65] = 1;

	s.push(temp);

 

dfs() 함수를 호출하게 되면 제일 먼저 시작 노드를 stack에 push 합니다. 

 

이때 stack에 push 되는 시작 노드는 좌측 상단이니 위치는 (0, 0)이고 부모 노드는 없으니 parent_num은 0이겠지요!

 

 alpha_visit[시작노드의 문자-65] = 1로 해주어 시작 노드의 알파벳을 지났음을 표시합니다. 

 

 

	while (!s.empty()) {
		temp = s.top();
		s.pop();
		flag = 0;

		for (int i = 0; i < 4; i++) {

			tx = temp.x + dx[i];
			ty = temp.y + dy[i];

			if (tx < 0 || tx >= c || ty < 0 || ty >= r)
				continue;

			int tmp = alpha[ty][tx] - 65;

			if (temp.alpha_visit[tmp] == 1) //지나온 알파벳이면 이동 X
				continue;

			node child; //자식 노드 생성 
			child.x = tx;
			child.y = ty;
			child.parent_num = temp.parent_num + 1;
			
            //부모 노드 temp가 지나온 알파벳들 자식 노드 child에도 복사 
			memcpy(child.alpha_visit, temp.alpha_visit, sizeof(temp.alpha_visit));
			child.alpha_visit[tmp] = 1;  //자식 노드 방문 표시

			if (flag == 0) { 
				flag = 1; //현재 노드 temp에서 이동 가능한 자식 노드가 있음을 나타내는 변수
			}
			s.push(child);
		}

		if (flag == 0) { //이동 가능한 자식 노드 없을 때 = 경로 끝났을 때 
			if (maxnum < temp.parent_num + 1) {
				maxnum = temp.parent_num + 1; //부모 노드의 개수=경로 길이
			}
		}

	}

 

 시작 노드를 push 하였으면 이제 탐색을 시작해줍니다!

 

 stack의 top 노드를 pop하여 현재 노드에서 이동가능한 위치 중 아직 지나오지 않은 알파벳을 자식 노드로 생성합니다. 

 

 자식 노드의 parent_num은 현재 노드의 parent_num+1 이겠지요!

 

 자식 노드의 alpha_visit[]은 현재 노드의 alpha_visit[]을 복사하여 현재 노드가 지나온 알파벳 경로 정보를 그대로 가져와야 합니다. 

 

 복사한 뒤 자식 노드 본인의 알파벳 방문 여부도 1로 해주어야겠지요!

 

 만약 이동 가능한 자식 노드가 없을 때는 해당 경로가 끝났음을 의미합니다. 이때 maxnum과 현재 노드의 부모 노드 수+1를 비교하여 더 큰 수를 maxnum으로 set 해줍니다. 

 

 

 

전체 코드입니다. 

#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<stack>
#include<cstring>

using namespace std;

char alpha[21][21];  //알파벳 맵
int r, c; //행, 열 수
int maxnum = 0;  //최대 길이

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

typedef struct node {
	int x, y;  //위치
	int parent_num;  //부모 노드 개수
	int alpha_visit[26] = { 0, };  //지나온 알파벳
}node;

void dfs() {

	int flag;
	int tx, ty;
	stack<node> s;
    
	node temp;  //시작 노드, 좌측 상단에 있는 노드
	temp.x = temp.y = temp.parent_num = 0;
	temp.alpha_visit[alpha[0][0] - 65] = 1;

	s.push(temp);

	while (!s.empty()) {
		temp = s.top();
		s.pop();
		flag = 0;

		for (int i = 0; i < 4; i++) {

			tx = temp.x + dx[i];
			ty = temp.y + dy[i];

			if (tx < 0 || tx >= c || ty < 0 || ty >= r)
				continue;

			int tmp = alpha[ty][tx] - 65;

			if (temp.alpha_visit[tmp] == 1) //지나온 알파벳이면 이동 X
				continue;

			node child; //자식 노드 생성 
			child.x = tx;
			child.y = ty;
			child.parent_num = temp.parent_num + 1;
			
            //부모 노드 temp가 지나온 알파벳들 자식 노드 child에도 복사 
			memcpy(child.alpha_visit, temp.alpha_visit, sizeof(temp.alpha_visit));
			child.alpha_visit[tmp] = 1;  //자식 노드 방문 표시

			if (flag == 0) { 
				flag = 1; //현재 노드 temp에서 이동 가능한 자식 노드가 있음을 나타내는 변수
			}
			s.push(child);
		}

		if (flag == 0) { //이동 가능한 자식 노드 없을 때 = 경로 끝났을 때 
			if (maxnum < temp.parent_num + 1) {
				maxnum = temp.parent_num + 1; //부모 노드의 개수=경로 길이
			}
		}

	}

}

int main(void) {

	cin >> r >> c;

	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++)
			cin >> alpha[i][j];
	}

	dfs();

	cout << maxnum;

	return 0;
}