kcm5680   8년 전

예제 답은 맞게 나오는데 채점에서 틀리게 나오네요..

무엇이 문제일까요 고수님들 답변좀 부탁드립니다.

indioindio   8년 전

3 3

111

111

111

일 때 5가 아니라 9를 출력하네요.

dfs로 푸실 계획이라면 모든 경로를 다 방문할 수 있어야 하는데,

위처럼 푸실 경우 map[x][y] = '0'에 의해 한 경로로만 쭉 가서 9를 출력하게 됩니다

slanjdu   8년 전

추가로 덧붙이자면 return 될때 다시 1로 만들어 줘야해요 그래야 다시 탐색 시작 해요 !

indioindio   8년 전

네 dfs로 푸시려면 윗 분 말씀대로 고치시면 될 것 같네요.

그러면 아마 시간초과를 경험하게 되실 것 같습니다..ㅠ

kcm5680   8년 전

답변 주셔서 감사합니다. 우선 dfs로 해보고 시간초과를 경험하고 다시 풀어야 할듯 같네요. 두분 모두 감사드려요!!! 

indoiindiod은 특히 답변 잘 달아주시네요 감사합니다 : D

kcm5680   8년 전

..  map에서 지나간 부분을 0으로 바꾸고 다시 1로 갔던길을 다시 1로 치환을 안해서 틀렸었네요..

문제를 해결하니 역시 indoiindoid님 말대로 시간초과 오류가 ㅡㅡ;;; 

깊이 탐색후 안간곳에 대해서 현재 최소값보다 큰 값은 가지치기를 해도... 채점 25% 정도에 시간 초과.....


가지치기를 더해야 하나요? 아님 다른 방법으로 풀어야 하나요...

꾸벅 질문에 대한 답변좀 부탁드리겠습니다...


indioindio   8년 전

dfs로 풀어보진 않아서 확답은 못 드리겠지만 가능하면 아래, 오른쪽으로 우선 움직이기, 입구에서 미로의 절반까지만 dfs로 방문하고, 출구에서 출발해서 나머지 절반까지 도달해서 dfs의 깊이 줄이기 등을 활용하면 시간 내에 될 지도 모르겠네요.

근데 제 생각에는 bfs로 이 문제를 푸시는 게 편할 것 같습니다. bfs로는 출구에 도착하는 순간 그게 최소거리임을 알 수도 있을 뿐더러 어떤 입력에도 비슷한 성능을 낼 것 같습니다. (dfs로 전부 다 개방된 미로를 풀게 되면 가지수가 꽤 많을 것 같네요)

slanjdu   8년 전

저도 처음에 탐색 공부했을때 dfs밖에 할줄몰라서 비슷하게 당했던 경험이 있는데요...

indioindio 님이 말씀하신대로 재귀의깊이를 줄이면 가능성이 있긴한데

입력하는 테스트케이스를 확인하면 dfs로 하면 타임리밋이 나는 경우를 입력받거든요...

예를들면 전부다 갈수있는 길로 체크된 경우 였었나? 그런 경우에는  mXn의 수만큼 재귀가 깊어져버려서.. 헤어나오지 못한다는... 

kcm5680   8년 전

bfs로 풀어봤는데.. 런타임 에러가나네요..

아마 큐에서 메모리가 계속 증가해서 그런 것 같은데.. 맞추신 분들은 어떻게 구현하셨나요 ㅠ?

indioindio   8년 전

현재 위치를 pos++이 아니라 적절히 deque해서 푸시면 될 것 같습니다.

kcm5680   8년 전

indioindio님 slanjdu님

너무 감사합니다.

맞았습니다 : D


사내 시험때문에 공부하고 있는데... 많이 어렵네요 공부하기가 

우선 재귀에 익숙해져 보려고합니다.. 그후 다이나믹 프로그래밍도 쫌 볼까하는데 

지금은 남의 코드를 역으로 손으로 그려가면 한줄한줄씩 어떻게 돌아가는지 보고 있습니다 ㅡㅡ;; 도저히 재귀코드만 보고 답을 유추도 못할뿐더라... 짜다가 debugging하는것도 장난아니네요.



고수님이신것 같은데 공부 팁좀 알려주시면 감사하겠네요 : D

indioindio   8년 전

맞으셨다니 다행이네요. 고수는 절대 아닙니다..ㅋㅋ

그래도 재귀함수에 대해서 약간 팁을 드리자면 재귀함수를 자기 자신을 호출하는 함수라고 생각하시기보다는, 점화식이라고 생각하시는 게 편할 것 같습니다.

일례로 a 기둥에 있는 N개의 원판을 a,b,c 의 기둥에서 c로 옮기는 하노이의 탑 문제를 생각해보시면, (풀어보셨는지 모르겠지만 안 푸셨다면 한 번 풀어보세요)

f(n, src, dst, mid)라는 함수를

    f(n-1, a, b, c)

    move 1 from a to c

    f(n-1, b, c, a)

로 해서 초기조건을 더해서 주로 풉니다.

이 코드를 f가 자기 자신을 호출한다고 생각해서 계속 인자를 적어나가면 밑도 끝도 없지만, 점화식이라고 생각하면 편해집니다.

f(n, src, dst, mid)를 어떻게 작동 하는지는 모르겠으나 n개의 원반을 src에서 dst로, mid를 이용해 아주 잘 옮겨주는 함수라고 해봅시다.

그럼 위 함수를 이용해서 n 개를 a에서 c로 움직이려면,

n-1개를 우선 a에서 b로 옮긴 다음 (f(n-1, a, b, c)를 하면 되겠죠? 어떻게 해서 잘 옮겨주는지는 모르겠지만)

맨 밑에 한 개를 a 에서 c로 옮긴 다음,

n-1개를 다시 b에서 c로 옮기면 됩니다. // f(n-1, b, c, a)

위의 예시처럼 어떤 함수가 부분문제를 잘 해결해준다고 가정하고 점화식을 작성하듯이 코딩을 해주면 쉽게 재귀함수에 접근하실 수 있을 것 같네요.

slanjdu   8년 전

kcm5680님 :) 알고리즘 공부하는 학생입니다..

저도 시작한지 얼마 안되서 아는건 많이 없어요.


S직군이신가보네요...부럽..

4월 시험 보시나요? 저도 입사하고 싶네요 흑

kcm5680   8년 전

네 S직군입니다..

사트를 보고 들어온 차수라서 알고리즘에 약하네요.. 사실 학생때도 약했고..


대외비는 못 말해드리지만, 궁금한점이나  있으면 알려드릴게요. : D 

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