글 읽기 - 제발 도와주세요.. 두 코드의 차이를 모르겠습니다(주석 있습니다!)

sihyun93 4년 전 0

안녕하세요... 고수님들 가르침 받고자 질문 올립니다.

저는 이 문제를 버튼을 10번 눌러보는 모든 경우의수를 체크하는 bruteforce 방식으로 해결을 했는데요.

그 과정에서 visited 배열을 써서 중복되는것을 막아 시간을 단축하고자 했습니다. (오른쪽 버튼을 누르고 바로 왼쪽 버튼을 누르는것 같은 행위는 의미가 없으니까요)

근데 계속 오답이 나와서 visited로 중복을 체크해 주는 부분(line 15번과 40번)을 없애니까 통과하네요..

혹시 같은 점을 또 방문해야 하는 경우가 있나요..?

질문 읽어주셔서 감사합니다. 답변 기다리고 있겠습니다!

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

char map[30][30];
bool visited[30][30][30][30];
int r, c, cnt, flag = 987654321; // flag는 답을 저장하는 변수
int dx[4] = { -1,1,0,0 }; //dir 배열
int dy[4] = { 0,0,1,-1 }; // dir 배열
void move(int depth,int x1, int y1, int x2, int y2) {
	if (depth >= 10) return; // 10번 넘으면 끝냄
	if (depth >= flag) return; // 답을 이미 찾았는데 depth가 답을 넘어가면 최소가 아니므로 끝냄
	int nx1, nx2, ny1, ny2; // 동전1 : (nx1,ny1) 동전 2: (nx2,ny2)
	visited[x1][y1][x2][y2] = true; // 중복 방문 check <- 이 부분을 없애주면 통과합니다
	for (int i = 0; i < 4; i++) {
		int f1 = 0, f2 = 0;
		nx1 = x1 + dx[i];
		nx2 = x2 + dx[i];
		ny1 = y1 + dy[i];
		ny2 = y2 + dy[i];

		if (nx1 < 0 || ny1 < 0 || nx1 >= r || ny1 >= c) f1 = 1;
		if (nx2 < 0 || ny2 < 0 || nx2 >= r || ny2 >= c) f2 = 1;

		if(f1 && f2) continue; // 둘다 떨어지면 continue
		if (f1 || f2) { // 하나만 떨어짐
			flag = min(depth + 1, flag); //성공
			return; // 성공하면 끝냄
		}
		if (map[nx1][ny1] == '#') { // 벽이면 좌표 원위치
			nx1 = x1;
			ny1 = y1;
		}
		if (map[nx2][ny2] == '#') { // 벽이면 좌표 원위치
			nx2 = x2;
			ny2 = y2;
		}
		if ((nx1 == nx2) && (ny1 == ny2)) continue;
		if (visited[nx1][ny1][nx2][ny2]) continue; // <- 이 부분을 없애주면 통과합니다
		move(depth + 1, nx1, ny1, nx2, ny2);
	}
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	pair<int, int> coin[2];
	cin >> r >> c;
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cin >> map[i][j];
			if (map[i][j] == 'o')
				coin[cnt++] = make_pair(i, j);
		}
	}
	move(0, coin[0].first, coin[0].second, coin[1].first, coin[1].second);
	if (flag == 987654321) cout << "-1\n";
	else cout << flag << "\n";
}

sait2000 4년 전 1

dfs는 어떤 상태에 최단거리로 도착한다는 보장이 없습니다. 예를 들어 지금처럼이면 아래 오른쪽 위로 움직이는 경우를 오른쪽으로 움직이는 경우보다 먼저 탐색할 거 같네요. 만약에 그렇게 움직인 결과가 같다면 오른쪽으로 움직이는 경우는 두 번 덜 움직이니까 나중에 두 번 더 움직일 수 있는데도 visited가 표시돼있어서 탐색을 안 하게 됩니다.

sihyun93 4년 전 0

아 그렇군요....하루종일 고민했는데 바보같네욬ㅋㅋㅋ

감사합니다 좋은하루 보내세요!

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

문제

문제

출처

ICPC

제발 도와주세요.. 두 코드의 차이를 모르겠습니다(주석 있습니다!)

sihyun93 4년 전 0

sait2000 4년 전 1

sihyun93 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말