4-D 질문입니다!!

작성한 질문수 1

0

안녕하세요 우찬님 ㅎㅎ

나름 잘 짜셨습니다. ㅎㅎ

다만..

먼저 vector를 이용해서 visited를 만들고 해당 부분을 find를 하게 되면 O(N)의 시간복잡도가 걸리게 됩니다.

조금은 비효율적인 코드가 되버리는 것이죠.

또한 push_back()만 있어버리면 해당 부분의 좌표만 "넣는" 경우의 수밖에 체크하지 못합니다.

예를 들어 A -> B -> C라는 경우의 수와 A -> B -> D라는 경우의수 (B는 다른 좌표에 있음. 예를 들어 한쪽 B는 왼쪽, 한쪽 B는 아래쪽) 이런 경우의 수를 체크하지 못합니다.

void dfs(int y, int x)
{
	visited.push_back(board[y][x]);

그래서 해당 부분의 경우의 수를 초기화해주는 pop_back() 필요합니다.

또한, visited.size()를 출력하고 있는데 그것은 정답이 아닙니다. 여러가지 경우의 수중에서 max값을 뽑아내느 로직이 필요하며 그 로직이 결여되어있습니다.

제가 한번 고쳐봤는데요. ㅎㅎ

이렇게 해보시겠어요?

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int height, width;

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

vector<char> visited;

char board[24][24];
int ret; 

void dfs(int y, int x)
{
	visited.push_back(board[y][x]);
    ret = max((int)visited.size(), ret);

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

		if (ny >= height || ny < 0 || nx >= width || nx < 0)
			continue;
		auto iter = find(visited.begin(), visited.end(), board[ny][nx]);
		if (iter != visited.end())
			continue;

		dfs(ny, nx);
	}
	visited.pop_back();
}

int main()
{
	cin >> height >> width;

	for (int i = 0; i < height; ++i) {
		for (int j = 0; j < width; ++j) {
			cin >> board[i][j];
		}
	}

	dfs(0, 0);

	cout << ret << endl;

	return 0;
}

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.