[일반] 오늘 카카오 코테 5번 문제 질문 해도 될까요?

[익명(114.205)]

코테 싫어 하시는 거 알지만 한번 여쭤볼게요.
그래프 탐색 할때 방문 했던 노드를 다시 재방문 해야 하는 문제를 해결하지 못했습니다.
어떻게 처리 하는게 맞았나요?

그리고 혹시 백준에서 이와 비슷한 문제는 태그를 뭘로 해야 찾을 수 있는지 궁금합니다.

[익명(125.128)]

미방문 / 방문해서 양이나 늑대 데리고감 / 방문한곳을 경로로 지나침

[익명(175.113)]

나도 별지랄 다 해보다 그냥 재귀함수 인자로 set 놓고 저기다 다음에 방문 가능한 노드 전달하면서 무지성으로 모든 경로 다 탐색함

[oo(210.103)]

난 이거 처음본 유형인데 비트마스크 + bfs로 품

[oo(210.103)]

비트로 방문한 동물들을 큐에 넣어 관리하면서 현재 데리고 있는 동물집합으로 다음 노드에 갈 수 있을 때 비트 or 하고 큐에 삽입 이런식으로 탐색함

[익명(211.210)]

이걸 무슨 유형? 이라고 부르긴 좀 그래. n 제한이 17이라서 그냥 뭔 지랄을 해도 풀려서... 별로 좋지 않은 문제라고 생각함. 이런 문제는 다시 풀어볼 가치가 없다고 생각해

[QWERTY(182.231)]

dp[state] = 방문한 노드의 상태값. 이거만 가지고 있어도 해결됨 어차피 상태값 안에 양이랑 늑대 수 다들어있어서 아직 방문 안된 애들중에 간선 연결된 애들로 방문해주면 됨 늑대랑 양의 수 같아지면 바로 나오고

[익명(211.250)]

vector states[1<

[익명(114.205)]

다들 설명 너무 감사한데 말로만 들으니 이해가 안되네요 ㅠ 코드가 나오면 그때 이해해야겠습니다

[익명(223.62)]

그냥 비트마스크 dp문제 풀어보고 다시 생각해보는거 추천함. 3~4문제 풀면 얼추 이해갈거임 저거 비트마스크 알면 누구나 풀 수 있게 만든 문제라