[C++] 백준(BOJ) - 1987 : 알파벳

01 Nov 2023 in Develop on C++, Algorithm Last modified at: 2023-11-17

인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.

• 문제
• 알고리즘
• 풀이
• 코드 1 : DFS
• 코드 2 : 비트마스킹
• 평가

문제

백준(BOJ) - 1987 : 알파벳(링크)

알고리즘

1. 완전탐색
2. DFS
3. 비트마스킹

풀이

1. 일반적인 DFS로 풀이
   • visited 일차원 배열에 알파벳을 방문처리 하고
   • 이미 방문처리된 visited 배열을 방문한 경우 백트래킹
2. 비트마스킹으로 풀이
   • 방문 처리 check or uncheck 과정 없이 매개변수에서 비트 합 연산자를 통해 함수 호출 가능

코드 1 : DFS

// BOJ-3197 : 백조의 호수
#include<bits/stdc++.h>
using namespace std;
#define y1 aaaa

const int max_n = 26;
const int dy[] = { -1,0,1,0 };
const int dx[] = { 0,1,0,-1 };

int n, m, visited[max_n], res = 0;
char a[max_n][max_n];

void dfs(int y, int x, int cnt)
{
	res = max(res, cnt);

	for (int i = 0; i < 4; i++)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny < 0 || nx < 0 || ny >= n || nx >= m) continue;
		int _nxt = (int)(a[ny][nx] - 'A');
		if (visited[_nxt] == 0)
		{
			visited[_nxt] = 1;
			dfs(ny, nx, cnt + 1);
			visited[_nxt] = 0;
		}
	}
	return;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> a[i][j];
		}
	}
	
	visited[(int)(a[0][0] - 'A')] = 1;
	dfs(0, 0, 1);

	cout << res << '\n';

	return 0;
}

코드 2 : 비트마스킹

// BOJ-3197 : 백조의 호수
#include<bits/stdc++.h>
using namespace std;
#define y1 aaaa

const int max_n = 26;
const int dy[] = { -1,0,1,0 };
const int dx[] = { 0,1,0,-1 };

int n, m, res = 0;
char a[max_n][max_n];

void dfs(int y, int x, int num, int cnt)
{
	res = max(res, cnt);

	for (int i = 0; i < 4; i++)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];

		if (ny < 0 || nx < 0 || ny >= n || nx >= m) continue;

		int _nxt = 1 << (int)a[ny][nx] - 'A';
		if ((num & _nxt) == 0) dfs(ny, nx, num | _nxt, cnt + 1); // 합 연산자를 매개변수에 집어넣어서 불필요한 연산을 제거
	}
	return;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> a[i][j];
		}
	}
	
	dfs(0, 0, 1 << (int)a[0][0] - 'A', 1);

	cout << res << '\n';

	return 0;
}

평가

• 대략적인 시간복잡도를 미리 계산 해보고 사이즈가 조금 크다고 생각되더라도 완전탐색, 백트래킹 밖에 해결법이 없다 싶으면 알고리즘 짜기 시작
• 비트마스킹을 활용한 문제풀이법에 대해 추가적인 포스팅 예정