저도 이 문제를 한달 전에 시도했다가 결국 그냥 넘어갔는데, 오늘 다시 도전해봤습니다!
저의 경우,
처음에 문제를 제대로 읽지 않은 관계로 두번째 조건이었던, '쓰레기 옆을 지나가는 칸의 수'의 의미를
'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로 하여 넣으면 더 좋은 답안이 될 것 같습니다 !
추가적인 설명이 필요하시다면 다시 알려주세요! 감사합니다 :)
kalmiaa 7년 전
안녕하세요.
50*50이라, dfs로 backtracking 하면 당연히 stack over flow 날거고, 조건문을 넣고 bfs로 하기에는 너무 case수가 많습니다..
혹시 약간이라도 힌트를 주신다면 감사하겠습니다.