kalmiaa   7년 전

안녕하세요.


50*50이라, dfs로 backtracking 하면 당연히 stack over flow 날거고, 조건문을 넣고 bfs로 하기에는 너무 case수가 많습니다..

혹시 약간이라도 힌트를 주신다면 감사하겠습니다.

algogogo   7년 전

저도 이 문제를 한달 전에 시도했다가 결국 그냥 넘어갔는데, 오늘 다시 도전해봤습니다!


저의 경우, 

처음에 문제를 제대로 읽지 않은 관계로 두번째 조건이었던, '쓰레기 옆을 지나가는 칸의 수'의 의미를

'S -> F로 가면서 옆에 닿아있던 쓰레기의 수'라고 잘못 해석해서 문제 방향을 잘못 잡았습니다.


저는 마주친 쓰레기의 수를 저장하는 vis[51][51] 배열과,

쓰레기를 스쳐 지나온 '.' 칸의 수를 저장하는 p[51][51] 배열을 만들었습니다.


초기 S 좌표를 큐 안에 넣고,

상하좌우 방향에서, 만난 쓰레기 수(g)와, 주변에 쓰레기가 있는 칸(pg) 여부를 계산 한 뒤에,

1차적으론 vis[nx][ny] 값보다 현재 계산된 g 값이 더 작을 경우에만 vis를 g값, p를 pg값으로 갱신하고 큐에 집어넣었습니다.

만약 위에서 vis[nx][ny] 값이 g값과 같을 경우에는, pg[nx][ny] 값과 pg 값을 비교하여 pg가 더 작을때 갱신하고 큐에 집어넣었습니다.

위의 과정은 priority Queue를 이용하여 pair쌍을 각각 g, pg로 하여 넣으면 더 좋은 답안이 될 것 같습니다 !

추가적인 설명이 필요하시다면 다시 알려주세요! 감사합니다 :)



algogogo   7년 전

간단한 test case를 첨부합니다 !

6 6
...g..
g.gFg.
g.....
gg.ggg
......
...S.g

답 : 0 3

10 8
...g.g.g
..Fggggg
.....g..
g.g.g.g.
.g.g.g.g
...g.g.g
g.g.gggg
........
g...g.S.
........

답 : 1 5


7 5
..Fg.
g.g..
..ggg
.g.g.
..S.g

답 : 0 4


감사합니다.

kalmiaa   7년 전

감사합니다.

우선 주신 힌트 정독해보고 방법을 찾아보겠습니다 ~^^

reiui9   7년 전

7 5
..Fg.
g.g..
..ggg
.g.g.
..S.g
답 : 0 4

이 예제는 N이 맞지않는데요?
5 5 로 바꿔야하는거 아닌가요?

답도 0 5 가 나오는것같네요..

kalmiaa   7년 전

죄송합니다. 풀었습니다.

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