minhas2   2년 전

안녕하세요

BFS로 1525번 퍼즐문제를 풀려고하는데

정답은 잘뜨는데 문제는 메모리, 작동시간이 너무길어서 코드자체가 가독성이 너무 안좋은것같습니다. ㅜㅜ

일단 메모리초과는 queue가 원인같은데 어느부분에서 정확히 메모리초과나는질 모르겠구

두번째는 작동시간인데.. -1이 뜨는경우(해결할수없는 경우)가 저는 모든 경우의수(최대깊이까지) 탐색을해서도 정답이 안나오면 -1이 뜨게끔했습니다.

근데 이렇게되면 최소 10초이상은 걸리는것같더라구요.. ㅎㅎ

해결불가능한경우를 처리하는 함수를 별도로 구현하고싶었는데 정확히 어떤경우에 해결불가능한질 감이 잡히지않습니다.

1 3 4

6 7 8

0 5 2

그리고

1 3 6

4 7 8

0 2 5

그리고

1 2 3

4 5 6

8 7 0

이 해결불가능한 경우인데 처음엔 세번째테스트케이스만 돌려보고

단순히 주변값이 전체적으로 증가하는형태와 반대로 감소하는 형태면 해결할수없는경우구나. 라고 생각했는데

이런저런 테스트케이스를 넣어보니 그건 아닌것같더라구요..


아시는대로만 알려주시면 감사하겠습니다.... 어떤 의견이든 다 저한텐 큰 도움입니다 ㅠㅠㅠㅠ


chogahui05   2년 전

123

045

678


이런 상태를 string으로밖에 표현을 하지 못할까요? 의외로 매우 작은 길이의 문자열에 대해서

오버 헤드가 꽤 되는 걸로 알고 있습니다. 나머진 조금 있다 답변 드리겠습니다.

다른 방법도 있을 거 같습니다. 힌트는 9진법..

876543210 (9)가 10진수로 어떻게 표현될까요??


물론 이 문제를 풀지는 않았습니다.

minhas2   2년 전

말씀해주신대로 일단 string대신 char*형으로 바꿔서 제출해봤습니당..

말씀하신것처럼 string이 오버헤드가 많은게 맞는거같애서 바꿔서해봤는데 여전히 메모리초과네요 ㅠ 음 예상은했지만..

오히려 new선언이 많아지면서 메모리가 더 커진것같은 느낌이에요.. ㅜㅜ 제 코딩이잘못된거겠지만욤

그리구 9진수로 바꿔서 생각해보는건 아직 답을못얻은거같습니당..

혹시 shift연산..같은건가요? 아직 제 코딩실력이 많이부족해서 논리적인 접근이 좀 어렵네요..ㅎㅎ

아무쪼록 좋은흰트 감사드립니다~!ㅎㅎ

chogahui05   2년 전

shift 연산은 2, 4, 8진수 같은 게 있을 때 고려할 수 있는 것이고요.

9진수는 사실 간단합니다. 예를 들어서

012435768이 있었다고 가정한다면 이를 9진수로 표현하면 이렇게 되겠죠.

0 * 9^8 + 1 * 9^7 + 2 * 9^6 + 4 * 9^5 + 3* 9^4 + 5 * 9^3 + 7 * 9^2 + 6 * 9^1 + 8 * 9^0


나머지는 set 같은 거에 대응시키면 될 듯 싶네요. 이미 방문했던 정점은 탐색하지 않는다는 규칙을 세우신다면..

그 다음은 탐색 문제인 듯 싶고요.


워낙 문자열의 오버헤드가 커요..

(제가 알기로는 작은 문자열도 27byte 정도 차지하는 걸로 알고 있습니다만..

자세한 건 레퍼런스 참고해 보시는 게 좋으실 듯 싶네요.)


9진수 876543210은 9진수 1000000000 보다는 작습니다. 이는 9^9이므로 int 범위 안에 들어오지요.

minhas2   2년 전

답변감사드립니다

근데 궁금한것이 생겼는데 9진수로 바꾸게되면 어떤장점이 생기나요?

만약 9진수로 변환하게되면 그것또한 char*에 값을넣게되는걸로 알고있는데

int형으로 바로 9진수 변환이 가능해서 궂이 char*형을 쓰지않아도 해결된다는 말씀이신가요?

만약 char*로 9진수변환해서 넣는형태면 오히려 가독성만 더 늦춰질것같은뎅.... ㅜ흠..

chogahui05   2년 전

아니면 어짜피 9칸이잖아요.

그러니까 그냥 10진수로 받아도 크게 상관은 없을 듯 싶습니다. 제가 너무 어렵게 생각했네요..


이동할 때에는

[3][3]짜리로 변환하고, 이동시키고 다시 [3][3]을 int로 변환시키면 됩니다.

임시적으로 [3][3]짜리 배열을 쓰는 것 뿐입니다. map에는 int형을 넣을 뿐입니다.

minhas2   2년 전

감사합니다 근데 변환시키는 과정이 메모리에는 효율적이지만 속도는 더 늦어지지않을까요..?

크게 지장없을려나 ㅎㅎ.. 아무쪼록 감사드립니다~!!복받으세욥!

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