• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

dx와 dy 배열 순서에 관해 질문이 있습니다!

21.10.04 11:28 작성 조회수 142

0

dx와 dy안에 배열 순서를 {int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };

이런식으로 바꿨는데 왜 답도 같이 바뀌는 건가요??

DFS로 계속 돌면 어차피 경로는 똑같이 가져야하는게 아닌가요???

 

답변 1

답변을 작성해보세요.

0

안녕하세요^^

배열순서를 바꿨다고 답이 달라지지 않을 겁니다.

풀코드를 올려주시면 좋겠습니다.

ismy123님의 프로필

ismy123

질문자

2021.10.07

배운걸 활용해서 코드를 짜봤는데 dx dy의 배열순서가 달라지면 값이 다르게 나와서 질문드립니다~!

이런 경우는 왜 그런지 모르겠어요,,,,

 

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

vector<vector<int>> map(201, vector<int>(201, 1));
vector<vector<int>> visited(201, vector<int>(201, 0));
vector<pair<int, int>> cctvx[4], cctvy[5];
int res = INT_MAX, n;
int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };

void DFS(int x, int y,int timer,int cctvi) {
	int xx, yy;

	if (x == n && y == n) {
		res = min(timer, res);
	}

	else {
		while (cctvx[cctvi][0].first <= x && x <= cctvx[cctvi][0].second&&cctvy[cctvi][0].first <= y && y <= cctvy[cctvi][0].second) {
			timer++;
			cctvi++;
			if (cctvi == 4)
				cctvi = 0;
		}
		for (int i = 0; i < 4; i++) {
			xx = x + dx[i];
			yy = y + dy[i];

			if (xx<1 || xx>n || yy<1 || yy>n) continue;
			if (map[xx][yy] == 0 && visited[xx][yy] == 0){
				visited[xx][yy] = 1;
				timer++;
				cctvi++;
				if (cctvi == 4)
					cctvi = 0;
				DFS(xx, yy,timer,cctvi);
				visited[xx][yy] = 0;
			}
		}
	}
}

int main() {
	cin >> n;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> map[i][j];
		}
	}
	cctvx[0].push_back(make_pair(0, n / 4));
	cctvx[1].push_back(make_pair(n - (n / 4), n));
	cctvx[2].push_back(make_pair(n - (n / 4), n));
	cctvx[3].push_back(make_pair(0, n / 4));

	cctvy[0].push_back(make_pair(0, n / 4));
	cctvy[1].push_back(make_pair(0, n/4));
	cctvy[2].push_back(make_pair(n - (n / 4), n));
	cctvy[3].push_back(make_pair(n - (n / 4), n));
	
	visited[1][1] = 1;
	DFS(1,1,0,0);

	if (res == INT_MAX) {
		cout << -1;
		return 0;
	}
	else
	cout << res;
	
	return 0;
}