1987 C++ 백준 그래프 문제

문제를 천천히 읽어보자....

대충 보면 R x C grid가 있고 이미 방문한 알파벳은 방문이 불가능하다.

최대로 멀리 갈 수 있는 경로를 찾아라? 이렇게 해석이 된다... 그렇다면 dfs를 도입해서 생각해보자.

 

일단 머리에 하나의 코드를 넣고, 나의 정답 코드와 비교를 해보자.

void dfs(int x)
{
	visited[x] = true;
	cout << x << " ";
	for (int i = 0; i < graph[x].size(); i++) // 인접한 노드 사이즈만큼 탐색
	{
		int y = graph[x][i];
		if (!visited[y]) // 방문하지 않았으면 즉 visited가 False일 때 not을 해주면 True가 되므로 아래 dfs 실행
            dfs(y); // 재귀적으로 방문
	}
}

void solve(int x, int y, int m) {

	visited[arr[y][x] - 'A'] = 1;
	if (ans < m)
		ans = m;

	for (int i = 0; i < 4; i++) {
		int cx = x + dx[i];
		int cy = y + dy[i];
		
		if (cx >= 0 && cy >= 0 && cx < w && cy < h) {
			if (visited[arr[cy][cx] - 'A'] != 1) {
				
				solve(cx, cy, m + 1);
			}
		}
	}
	visited[arr[y][x] - 'A'] = 0;
}

생긴거만 보면 거의 동일하며, 문제에 맞게 조금만 변형이 되어 있다.

 

#include <iostream>
#include <vector>

using namespace std;

char arr[21][21];
int visited[26] = { 0, };
int ans = 1;
int h, w;

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

//dfs 돌리면서 계속 m과 ans의 값을 비교하며 업데이트한다.
void solve(int x, int y, int m) {

	visited[arr[y][x] - 'A'] = 1;
	if (ans < m)
		ans = m;

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

		

		if (cx >= 0 && cy >= 0 && cx < w && cy < h) {
			if (visited[arr[cy][cx] - 'A'] != 1) {
				
				solve(cx, cy, m + 1);
			}
		}


	}
	visited[arr[y][x] - 'A'] = 0;

}

int main() {
	

	cin >> h >> w;

	for (int i = 0; i < h; i++) {
		for (int k = 0; k < w; k++) {
			cin >> arr[i][k];
		}
	}

	solve(0,0,1);

	cout << ans;

	return 0;
}