글 읽기 - dfs 반례가 있을까요?

112ckek 4년 전 1

예제는 다 맞는데 틀렸네요..

도움 주시면 감사하겠습니다.

#include <iostream>
#include <vector>

using namespace std;

char dot[51][51];
bool check[51][51]; // true이면 갈 수 있는 곳
vector<pair<int, int>> list[51][51]; // 인접리스트

bool dfs(pair<int, int> from, pair<int, int> start, int depth){ // 지금 있는 곳, 처음 시작점, 깊이
	bool ret = false;
	check[from.first][from.second] = false;
	depth++;
	for(pair<int, int> to : list[from.first][from.second]){
		if(to == start && depth >= 4){ // 사이클 조건
			ret = true;
			break;
		}
		if(!check[to.first][to.second]) continue; // 가려는 곳의 check가 false이면 continue
		if(dfs(to, start, depth)){
			ret = true;
			break;
		}
	}
	check[from.first][from.second] = true;
	return ret;
}

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

	int N, M; cin >> N >> M; 
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= M; j++){
			cin >> dot[i][j]; // 상태 입력, check 초기화
			check[i][j] = true;
		}
	}
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= M; j++){
			if(i < N && dot[i][j] == dot[i + 1][j]){ //인접리스트 채우기
				list[i][j].push_back({i + 1, j});
				list[i + 1][j].push_back({i, j});
			}
			if(j < M && dot[i][j] == dot[i][j + 1]){
				list[i][j].push_back({i, j + 1});
				list[i][j + 1].push_back({i, j});
			}
		}
	}
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= M; j++){
			if(dfs({i, j}, {i, j}, 0)){
				cout << "Yes" << '\n';
				return 0;
			}
		}
	}
	cout << "NO" << '\n';
	return 0;	
}

sait2000 4년 전 3

60번 줄이 이상하네요

112ckek 4년 전 0

헐ㅋㅋㅋㅋ 너무 감사합니다!

kcc9827 3년 전 0

ㅋㅋㅋㅋㅋ 저도 ㅋㅋㅋㅋㅋㅋ

workhardslave 3년 전 0

헐 감사합니다 ㅋㅋㅋㅋㅋ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

dfs 반례가 있을까요?

112ckek 4년 전 1

sait2000 4년 전 3

112ckek 4년 전 0

kcc9827 3년 전 0

workhardslave 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말