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

이효민님의 프로필 이미지
이효민

작성한 질문수

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

2주차 개념 #9. 깊이우선탐색(DFS, Depth First Search)

dfs 탐색 순서

해결된 질문

작성

·

177

0

안녕하세요 큰돌님 dfs 공부하다가 탐색 순서가 헷갈려서 질문 드립니다. 제가 아래에 코드 링크를 첨부했는데요. 아래 그림에서 탐색 순서가 왜 저렇게 나오는지 모르겠습니다 ㅜㅜ

 

http://boj.kr/f89c319ec14048a2a042c5a4c7027d60

 

 

답변 1

1

큰돌님의 프로필 이미지
큰돌
지식공유자

안녕하세요 효민님 ㅎㅎ

그림 너무 잘그리시네요. ㅎㅎ

일단은..

	for(int i=0; i<4; i++){
		int ny= y+dy[i];
		int nx= x+dx[i];
		
		if(nx>n || nx <0 || ny>n || ny <0 || mp[ny][nx]==0) continue;

이부분이 있죠?

즉, 배열의 범위를 벗어나면 continue를 하게 됩니다.

dy = -1, dx = 0 이 의미는 2차원 배열에서 "위"로 간다는 의미입니다.

간단하게,

1 2

3 4

라는 2차원 배열 있다고 할게요.

1은 a[0][0]이죠?

3은 a[1][0]이죠?

즉, 우리가 코드로 구현한 2차원 배열의 세상에서는 아래는 +1입니다.

위는 -1이 되게 됩니다.

 

그렇기 때문에 처음에는 위로 가게 되는 것인데 배열의 범위를 벗어나게 되니 해당부분은 동작하지 않게 되고,

그 다음 수인 오른쪽으로 가고 아래, 왼쪽...

이렇게 탐색하게 되는 것입니다.



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

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

감사합니다.

강사 큰돌 올림.


이효민님의 프로필 이미지
이효민

작성한 질문수

질문하기