2-A, bfs dfs 로직에 대한 질문
안녕하세요, 선생님. 이번 문제와 bfs, dfs 전반적 로직 관련해서 질문있습니다!!
일단 이번 문제 정답 코드는 다음과 같습니다.
http://boj.kr/f3c01a8b5af34478acc8344f21094f9a
크게 바뀐거 없이, continue 조건문에서 범위체크하는 조건을 한번 빼봤습니다. 그런데도 정답에는 문제가 없더라구요.
bfs든 dfs든 시작점에서 시작해서 상 우 하 좌 순으로 돌면서 탐색을 진행할텐데, 항상 경우에 따라 이차원배열의 모서리부근에서는 out of bound위험이 있고,
이걸 그냥 복잡하게 고민안하고, 위험을 최소화 하기 위해서
!bound -> continue 조건을 깔고 들어가는걸로 이해하고있습니다. 그런데, 위와같은 코드의 경우에는, 조건을 안걸면 분명히
(-1, 0) 다시말해 out of bound 오류가 발생해야 할거같은데, 정답처리되는 이유를 잘 모르겠습니다.
+) 또한, 강의중에 꼭 범위체크 뒤에 ||로 map에서 0이면 continue를 걸어야 한다고 하셨는데,
이 이유도 왜 그런지 잘 모르겠습니다. 저희가 항상 시작할 때,
map 전체를 0으로 초기화.
조건에 맞게 map만들기.
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문으로 처리한다" 라고 일반화하고 진행해도 괜찮을까요?
답변 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





