백준 1987 [c++] 알파벳

그냥 bfs로 풀었는데 3번 테스트 케이스를 보고 생각해보니 당연히 DFS 문제였다.

bfs 풀이.

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <queue>

using namespace std;

int row;
int col;

char graph[21][21];

map<char, int> m;

bool isVisited[21][21] = { false, };
int cnt[21][21] = { 0, };

queue<pair<int, int>> q;

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

void bfs(int startX, int startY) {
	q.push({ startX,startY });
	isVisited[startX][startY] = true;
	m[graph[startX][startY]]++;
	cnt[startX][startY] = 1;
	cout << graph[0][0] << " ";
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

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

			if (nx < 0 || ny < 0 || nx >= row || ny >= col) continue;
			if (isVisited[nx][ny]) continue;
			if (m.count(graph[nx][ny]) != 0) continue;

			m[graph[nx][ny]]++;
			cout << graph[nx][ny] << " ";
			q.push({ nx,ny });
			isVisited[nx][ny] = true;
			cnt[nx][ny] = cnt[x][y] + 1;

		}
	}
}

int main() {
	cin >> row >> col;


	for (int i = 0; i < row; i++) {
		string sTmp;
		cin >> sTmp;
		for (int j = 0; j < sTmp.size(); j++) {
			graph[i][j] = sTmp[j];
		}
	}

	bfs(0, 0);

	int max = -987654321;

	for (int i = 0; i < row; i++) {
		for (int j = 0; j < col; j++) {
			if (max < cnt[i][j])
			{
				max = cnt[i][j];
			}
		}
	}

	cout << max;

	return 0;
}


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

DFS 정답 풀이

#include <iostream>
#include <vector>
#include <string>
#include <map>

using namespace std;

int row, col, ans = 0;
char graph[21][21];
map<char, bool> visited;

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

void dfs(int x, int y, int depth) {
    ans = max(ans, depth);

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx < 0 || ny < 0 || nx >= row || ny >= col)
            continue;
        if (!visited[graph[nx][ny]]) {
            visited[graph[nx][ny]] = true;
            dfs(nx, ny, depth + 1);
            visited[graph[nx][ny]] = false;
        }
    }
}

int main() {
    cin >> row >> col;

    for (int i = 0; i < row; i++) {
        string sTmp;
        cin >> sTmp;
        for (int j = 0; j < col; j++) {
            graph[i][j] = sTmp[j];
        }
    }

    visited[graph[0][0]] = true;
    dfs(0, 0, 1);
    cout << ans;

    return 0;
}