3-K 코드 질문있습니다

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

3-K와 문제의 단순화

작성

수정됨

안녕하십니까 큰돌님.

3-K 질문들을 보니 대부분 시간 초과가 나는데 저 역시도 마찬가지입니다.

얼음 녹이기 -> 백조 이동 -> 백조끼리 만나면 종료.

위 같이 로직을 생각했습니다. 강의 보기 전에 작성했던 건데

http://boj.kr/94d4853fa89a44a7afbde319de126610

제 코드에서 불필요한 로직이 있는 건 확실한데 어딘지 정확하게는 모르겠는데 피드백 주시면 감사합니다.
melting() 함수에서 얼음을 녹인 지점을 wTmp 에 저장하고,
go() 함수 이후에 백조끼리 만나지 못했다면
wList=wTmp 를 통해 녹인 지점부터 반복을 하게 만들었습니다. "재귀적으로 영역을 탐색하는 거나 queue 등을 이용해 단계적으로 탐색해가는 것 이 2가지 모두 플러드필" 이라고 큰돌님 답변을 봤는데, 저도 플러드필을 사용한 건가요 ??

모든 문제에서 그런 것은 아니지만 이 문제에서만큼은 dfs는 원하는 지점에 가기까지 불필요한 방문을 많이해서 bfs가 더 효율적이다 라고 받아들이면 되는 것이죠 ??

c++코딩-테스트

답변 2

대기업목표

질문자

친절하고 자세한 답변 감사드립니다 !!

재귀적으로 영역을 탐색하는 거나

-> 혹시 제가 어디서 그랬는지 알 수 있을까요?

https://www.inflearn.com/community/questions/670682

여기 답변에서 읽었습니다.

큰돌

지식공유자

아 그랬군용...

이렇게 이해하시면 될 것 같습니다.

플루드필은 단계별로 색칠하는 알고리즘을 의미합니다.

이 때 보통은 BFS기반의 queue 두개를 기반으로 단계적으로 색칠하는 알고리즘이나 DFS로도 구현이 가능합니다. (백준 - 치즈문제생각하시면 됩니다.)

말씀해주셔서 감사합니다.

큰돌

지식공유자

안녕하세요 대기업님ㅎㅎ

먼저 코드리뷰입니다.

            if (a[i][j] == 'L') {
                lList.push_back({i, j});

이거 L 밑에 물입니다. wList에도 담아야 해요

    while(true) {
        go(l_y, l_x);
        if (flag) break;
        memset(lvisited, 0, sizeof(lvisited));

이게 비효율적이죠.

어떤 느낌이냐면요.

a -> b

a -> b -> c

a -> b -> c -> d

이렇게 되요. 즉, 탐색한 지점을 다시 방문하게 되는 로직입니다.

queue 등을 이용해 단계적으로 탐색해가는 것 이 2가지 모두 플러드필"

-> 플러드필은 2가지 의미로 쓰이는데요.

첫번째. 컴포넌트들을 번호를 붙여가며 색칠하는 알고리즘

두번째, queue를 2개를 사용하거나 qSize를 통해 단계적으로 BFS하는 것을 얘기합니다.

dfs는 플러드필이 아닙니다.

재귀적으로 영역을 탐색하는 거나

-> 혹시 제가 어디서 그랬는지 알 수 있을까요?

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

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

감사합니다.

강사 큰돌 올림.

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

3-K 코드 질문있습니다