백준2210 - 숫자판 점프

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

2210번: 숫자판 점프

BFS를 활용하여 푼 문제다. 행렬에서 방문한 곳도 재방문이 가능하도록 문제 조건을 주었다. 현재까지 탐색한 숫자의 갯수가 6개이면 6자리 숫자로 바꾸고 그 숫자를 탐색하였는지 체크하여 탐색을 하지 않았더라면 탐색을 하였다고 체크를 하고 카운팅을 +1 해주면 된다.

#include <iostream>
#include <queue>
#include <string.h>
#include <string>
using namespace std;

bool visit[1000000];
int cnt = 0;
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
string mat[5][5];

void bfs(int x, int y) {
	queue<string> q; //숫자들을 탐색한 결과
	queue<pair<int, int>> index; //탐색한 행렬에 좌표

	q.push(mat[x][y]);
	index.push(pair<int, int>(x, y));

	while (!q.empty()) {
		//맨 앞에 숫자 탐색 결과와 좌표값을 미리 저장
		string temp = q.front(); 
		int tempx = index.front().first;
		int tempy = index.front().second;

		//맨 앞에 원소 제거
		q.pop();
		index.pop();

		//6자리 숫자면
		if (temp.size() == 6) {
			int now = stoi(temp);
			if (!visit[now]) { //현재 있는 공간이 방문하지 않은 숫자이면
				cnt++; //숫자의 종류를 1증가시키고
				visit[now] = true; //방문 처리
			}
			continue; //현재 방문한 원소 종료
		}

		//4방향으로 방문한 곳도 재방문이 가능
		for (int i = 0; i < 4; i++) {
			int nx = tempx + dx[i];
			int ny = tempy + dy[i];
			if (0 <= nx && nx < 5 && 0 <= ny && ny < 5) { //좌표의 범위가 유효하면
				q.push(temp + mat[nx][ny]); //현재까지 찾은 숫자 원소를 삽입
				index.push(pair<int, int>(nx, ny)); //현재 이동 가능한 좌표의 위치를 삽입
			}
		}
	}
}

int main() {
	//6자리 숫자를 모두 미방문 처리
	memset(visit, false, sizeof(visit));

	//좌표 입력
	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {
			cin >> mat[i][j];
		}
	}

	//25칸 모두를 탐색하여 6자리 숫자가 되는 경우를 찾는다.
	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {
			bfs(i, j);
		}
	}

	cout << cnt;
}