백준 알파벳 1987 (비트) ❗

CJB_ny·2023년 3월 3일
0

백준

목록 보기
94/104
post-thumbnail

알파벳


분석

밟은 알파벳은 다시는 못밟고 최대한 깊숙이 들어갈 때 그 깊이 값을 구하는 문제이다.

본인은 DFS로 품.

후기

이전에 풀었던 문제인데 DFS말고 다른 방법이 생각이 안나서 다시 DFS로 풀었는데

이 문제는 DFS + 비트 마스킹으로 visited와같은 배열을 관리하지 않고 풀 수가 있었다.

'&' 연산자로 방문했는지 안했는지를 확인하고

| 연산자로 방문처리를 한뒤 방문한 값을 인자로 넘기는 식이다.

Code

#include <iostream>

using namespace std;

#define endl "\n"

int r, c, ret, ny, nx;
char arr[21][21];
const int dy[] = { -1, 0, 1, 0 };
const int dx[] = { 0, 1, 0, -1 };

bool Cango(int y, int x)
{
	if (y < 0 || x < 0 || y >= r || x >= c) return false;
	return true;
}

void Go(int y, int x, int num, int cnt)
{
	ret = max(ret, cnt);
	for (int i = 0; i < 4; ++i)
	{
		ny = y + dy[i]; nx = x + dx[i];
		if (Cango(ny, nx) == false) continue;
		int _next = (1 << int(arr[ny][nx] - 'A'));

		// & 연산으로 방문했는지 안했는지 확인
		if ((num & _next) == 0)
		{
			// 방문하지 않았다면 or 연산자로 방문처리.
			Go(ny, nx, num | _next, cnt + 1);
		}
	}
}

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

	ret = -1;

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

	Go(0, 0, 1 << (int)(arr[0][0] - 'A'), 1);
	cout << ret << endl;

	return 0;
}
profile
공부 일기장으로 변해버린 블로그 (https://cjbworld.tistory.com/ <- 이사중)

0개의 댓글