ikth6001   4년 전

안녕하세요 열심히 알고리즘 공부 중인데요... 구슬탈출2 문제 뭐가 틀렸는지 모르겠어서 조언좀 구합니다.
대부분 풀이를 보면 BFS로 풀었던데 저는 재귀호출을 통한 DFS로 풀어봤습니다.
알고리즘을 간단히 설명 드리면,

1. 위로 움직인다고 가정했을 때 파란 구슬이 구멍에 닿으면 안 움직임.
2. 1번이 아닌 상태에서 위로 움직인다고 가정했을 때 빨간 구슬이 구멍에 닿으면 완료. cnt 등록
3. 1, 2번이 아닌 상태에서 위로 움직였을 때 구슬의 이동이 있는지 검사
4. 구슬의 이동이 있다면 visit 배열에서 빨간, 파란 구슬의 이전 이력 중 움직인 위치에 중복 되는지 확인
5. 4번이 아니라면 다시 메소드를 재귀호출하여 DFS 시작

이렇게 알고리즘을 구현 해봤습니다. 특별히 문제점은 없는것 같은데... 67% 정도에서 틀린답이라고 나오네요
조언 주시면 감사하겠습니다.


ikth6001   4년 전

어쩌다 보니 해결 했습니다만 이해는 안가네요
게시판의 질문들을 보다보니 visit 여부를 체크하는 로직을 RED와 BLUE를 별도 배열로 나누어서 처리하면 틀렸다고 나오고 하나로 합치면 정답으로 나온다는 얘기가 있어서
visit 여부 체크하는 아래 로직을 지웠더니 맞음으로 처리 되었습니다.
음 근데 위에 visit 여부를 체크하는 로직(105라인)이 뭐가 잘못된건지는 아직도 모르겠네요...ㅜ

whgusdn321   4년 전

visit을 채크 하면 안됩니다.

코드를 자세히 보지는 못했는데요,  아마 맥락상 파란공이나 빨간공이 이때까지 온 경로를 다시 되돌아 갈 수 없다고 하신건가요?

만약 처음 오른쪽으로 공이 쭉 갔다가 그 바로 다음번에 왼쪽으로 쭉 가서 방문했던 곳을 방문하면 안되지만, 오른쪽으로 갔다 윗쪽으로 갔다 왼쪽으로 갔다 다시 밑쪽으로 내려와서 다시 만난다면( 즉, 바로 왼쪽으로 가는게 아닌 몇번 다른방향으로 갔다가 다시 만나면) 가능한 경우입니다.

코드를 안보고 답변하는거라 전혀 쌩뚱맞은 답변일지도 모르겠습니다

댓글을 작성하려면 로그인해야 합니다.