인프런 커뮤니티 질문&답변

ismy123

작성한 질문수

it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비

65. 미로탐색 (2차원 배열 DFS)

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

작성

268

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

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

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

C++코테 준비 같이 해요!

퀴즈

재귀 함수가 호출될 때, 함수의 지역 변수, 매개변수, 복귀 주소 등의 정보는 어떤 자료구조에 저장되어 관리될까요?

큐 (Queue)

스택 (Stack)

배열 (Array)

연결 리스트 (Linked List)

답변 1

김태원

지식공유자

안녕하세요^^

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

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

ismy123

질문자

배운걸 활용해서 코드를 짜봤는데 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;
}

ismy123

작성한 질문수

전체 Q&A

질문하기