dhseo89   5년 전

안녕하세요 도저히 혼자 못찾겠어서 질문 올립니다..ㅜㅜ

제출하면 맞는거 까지 나오는데 시간이 너무 많이 걸리더라구요

3 4

0 2 0 2

1 1 0 1

1 1 0 1

이 반례 넣으면 벽을 세울수 있는 경우의 수가 총 4가지인데

저는 한번을 중복해서 5번을 돌더라구요... y>N-1 여기서 x+1 해주는 부분이 의심되긴하는데

정확히 문제가 어디고 어떻게 고쳐야하는지 모르겠어서 질문올립니다 ㅜㅜ

seico75   5년 전

dfs 함수의 정의가 뭔지가 확실해야할 것 같습니다.

main 에서 호출하는 것을 보면.. dfs(x, y, cnt) 는 "x, y 에 벽을 세웠으니 그 이후에 벽을 세워서 답을 찾아줘" 가 되고.. (근데 그래도 cnt 의 의미가 좀...)

dfs 내에서 재귀하는 것을 보면.. "x,y 부터 벽을 놓을 있는 곳을 찾아가면 답을 찾아줘"가 됩니다.

결국 벽을 누가 찾는지가 양쪽에 걸쳐저 있어서 dfs 내의 재귀에서 찾은 곳을 main 의 루프에서 또 되는 상황이 생깁니다. 

설명이 좀 어렵네요..

그래서 

main 의 루프를 없애고 (0, 0, 0)으로 호출하거나...   https://ideone.com/gt4gbY

dfs 내에서 루프를 돌면서 0인 곳을 찾아서 재귀호출을 하거나..    https://ideone.com/V3NTHp

둘 중의 하나로 가야할 것 같습니다.

dhseo89   5년 전

감사합니다 도움이 많이 되었어요~

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