inflearn logo
강의

강의

N
챌린지

챌린지

멘토링

멘토링

N
클립

클립

로드맵

로드맵

지식공유

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

2-A

2-A, bfs dfs 로직에 대한 질문

해결된 질문

124

ghtkdrla321

작성한 질문수 3

0

안녕하세요, 선생님. 이번 문제와 bfs, dfs 전반적 로직 관련해서 질문있습니다!!

일단 이번 문제 정답 코드는 다음과 같습니다.

http://boj.kr/f3c01a8b5af34478acc8344f21094f9a

크게 바뀐거 없이, continue 조건문에서 범위체크하는 조건을 한번 빼봤습니다. 그런데도 정답에는 문제가 없더라구요.

bfs든 dfs든 시작점에서 시작해서 상 우 하 좌 순으로 돌면서 탐색을 진행할텐데, 항상 경우에 따라 이차원배열의 모서리부근에서는 out of bound위험이 있고,

이걸 그냥 복잡하게 고민안하고, 위험을 최소화 하기 위해서

!bound -> continue 조건을 깔고 들어가는걸로 이해하고있습니다. 그런데, 위와같은 코드의 경우에는, 조건을 안걸면 분명히

(-1, 0) 다시말해 out of bound 오류가 발생해야 할거같은데, 정답처리되는 이유를 잘 모르겠습니다.

 

+) 또한, 강의중에 꼭 범위체크 뒤에 ||로 map에서 0이면 continue를 걸어야 한다고 하셨는데,

이 이유도 왜 그런지 잘 모르겠습니다. 저희가 항상 시작할 때,

  1. map 전체를 0으로 초기화.

  1. 조건에 맞게 map만들기.

  2. dfs/bfs

이런식으로 진행되는데, 범위를 벗어난 지역은 어차피 visited도 false, 맵에도 0으로 표시되는게 보장될텐데,

순서를 바꾼다고 해서 문제가 발생하는 일이 일어나나요?

=> 이게 범위 관련 이슈때문에 범위를 맨 앞으로 빼야할것 같다는 생각이 들었습니다...

 

 

두번째로, bfs dfs 구현상 질문입니다.

문제들의 경우에 따라서, if ~~ continue;

if ~~ continue를 두번씩 사용하시는 경우를 봤습니다.

(이번문제도 그렇습니다)

이건 continue의 특성상, 아래라인에 else if를 안걸어도

(컴파일러가 알아서 해줄지는 모르겠지만)

else if를 거는듯한 최적화의 효과를 얻을 수 있겠다고 보이긴 합니다.

 

그런데, 저런식으로 continue문을 여러줄에 걸쳐서 쓴다는건,
if ~~~ continue; (1조건)

if ~~~ continue; (2조건)

이렇게 1조건으로 필터링 하고, 1조건에 안걸리는 (여집합) 대상들에 대해 2차적인 필터를 하는걸로 생각이 드는데,

"이제부터 항상 continue관련 조건은 다 ||로 엮어서 한 if문으로 처리한다" 라고 일반화하고 진행해도 괜찮을까요?

c++ 코딩-테스트

답변 1

0

큰돌

안녕하세요 ㅎㅎ

(-1, 0) 다시말해 out of bound 오류가 발생해야 할거같은데, 정답처리되는 이유를 잘 모르겠습니다.

>> C++에서 배열의 범위를 벗어난 접근은 정의되지 않은 동작(UB, Undefined Behavior)을 일으킬 수 있습니다. 지금은 통과가 되지만 다른 컴파일러나 다른 문제에서는 특정하게 오류가 발생할 수 있는 코드입니다.

 

순서를 바꾼다고 해서 문제가 발생하는 일이 일어나나요?

>> 배열을 a[10]으로 선언했는데 a[11]을 참조하거나a[-1]을 참조하는 것은 앞서서 막아야 합니다. UB가 발생할 수 있기 때문입니다. 그래서 범위체크 -> 방문체크 이렇게 들어가야 합니다.

if ~~~ continue; (1조건)

if ~~~ continue; (2조건)

>> 네 잠습니다. 앞의 코드는 다음과 같이 해도 됩니다.

if (조건1 || 조건2) continue;

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

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

감사합니다.

강사 큰돌 올림.


살구 클럽에 대한 질문있습ㄴ디ㅏ

0

8

0

교안 158페이지 문의드립니다

0

25

2

코딩살구클럽 관련 건의사항

0

57

1

코살에 19942 다이어트 문제에 N의 범위가 빠져있슴니다

0

27

1

진행 방법 질문드립니다!

0

58

2

2-I) 왜 이 문제가 그래프이론 카테고리에 있는지 잘 모르겠습니다.

0

59

2

2주차 개념#12 트리 순회

0

29

2

백준사이트가 종료된다고 합니다.

0

289

2

백준 서비스 종료

9

894

1

sk 하이닉스 코테 대비

0

370

2

3-G 최댓값 질문

0

51

1

모듈러 연산 값이 10이 아닌 경우도 있지 않나요?

0

83

2

3-I 코드 질문드립니다.

0

62

2

3-N 질문 있습니다.

0

66

2

학습방법

0

102

2

4-H 질문 있습니다 (코드 리뷰)

0

66

2

코딩테스트 어디까지 준비해야 하는지 질문이 있습니다.

0

173

2

2-O 반례가 무엇일지 어떤 부분이 틀렸는지 잘 모르겠습니다.

0

69

2

2주차 개념 #4-2. 인접행렬 질문있습니다.

0

64

2

1-A 문제풀이 후 궁금한 점이 생겨서 질문드립니다.

0

51

2

조합 재귀 풀이 확인 해주시면 감사하겠습니다.

0

68

2

함수별 시간복잡도

0

74

2

3-h 질문입니다.

0

49

1

안녕하세요 선생님. 시간 복잡도 4번 질문있습니다.

0

53

2