busyhuman   1년 전

메모이제이션이 잘못된건가요?

코드를 수정하실때는 되도록이면 이해하기 쉽도록 고치는게 좋은데 우선 이 코드에서는 dfs부분에서 일일이 다 +1, -1 하는것 보다는 방향배열을 쓰시는게 좋을것 같습니다. 예를 들어서 어느 한 위치에서 (i, j)에서 상하좌우를 가고 싶다면 아래처럼 하는게 더 가독성이 있지 않을까요??? 그리고 어떤 위치가 어떤 범위안에 있는지 확인하는것은 많이 쓰기 때문에 따로 범위안에 있는지 확인해주는 함수를 만드시면 좋을 것 같습니다. 그렇게 해서 코드를 수정하시면 문제점을 찾기가 더 쉬울것 같습니다.

그리고 visit 배열과 dp배열을 합치는 것도 좋을 것 같습니다. 예를 들어서 visit 했는지 않했는지는 dp배열의 값이 어느 특정값(코드에서는 -200000000)인지 아닌지로 확인 할수 있기 때문에 굳이 할 이유는 없을 것 같습니다.

그리고 dfs함수 안에서 if를 else if로 고쳐야 할 듯 합니다.  

그리고 dp[y][x] + arr[y + 1][x] > dp[y + 1][x] 이런식으로 하면 예외가 생길 수 있습니다.

0 0 0 0 0

0 -1 -1 -1 -1

-1 -1 -1 -1 987654321

-1 -1 -1 -1 -1

이 경우에서는 987654321을 둘러싼 수가 음수이므로 987654321까지 않기 때문에 예외가 생길 수 있습니다. 그리고를 너무 많이 썼네요...ㅋㅋㅋ

busyhuman   1년 전


seanrocket17_2

 1. dfs부분에서 일일이 다 +1, -1 하는것 보다는 방향배열을 쓰시는게 좋을것 같습니다. 

-> 그 방법을 알긴 아는데 노가다하는게 습관이 되었습니다. 되도록 간단하게 짜도록 노력해야 겠습니다.

2. visit 배열과 dp배열을 합치는 것도 좋을 것 같습니다.

-> 네 수정하겠습니다.

3.dfs함수 안에서 if를 else if로 고쳐야 할 듯 합니다.  

-> 그러면 탐색을 다 못하지 않나요?

탐색을 하기는 하지만 너무 비효율적입니다..

참고로 저는 x를 행으로 y를 열로 씁니다.

저라면 코드를 아래처럼 짤것 같습니다.

저도 busyhuman 이 질문하시고 저도 이 문제를 풀고 싶어져서 저도 이 문제를 한번 같이 풀어보겠습니다.

busyhuman   1년 전

seanrocket17_2

아까 전에 재귀로 안되서 반복문으로 풀긴했는데.. 여전히 재귀의 한이..

꼭 재귀로 풀고 싶으시면 재귀로 푼 다른 사람의 코드를 참고해보시고 스스로 한번 짜 보시는게 좋을듯 합니다.

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