이 알고리즘은 BFS?DFS?시뮬레이션? 어떻게 접근해야함??

[BOJ(110.9)]

2015년도 삼성코딩문제인데.. 10번이내에 뺄 수 있냐 없냐만 물어보는거면

WHILE(10번--){
1.상/하/좌/우로 각각 R,B의 위치값을 변화시킴

2.변화된 좌표값과 횟수를 큐에 같이보관함

3.이렇게 10번이내에 한번이라도 성공한다면 1출력->BREAK 10번되도 안나오면 WHILE문바깥에서 0출력

이렇게 접근하려고하는데 이렇게 하는게 맞나?

왠지 이런 시뮬레이션은 DFS로 해야할거같은데 DFS는 잘 못다뤄서...방법좀

[익명(223.62)]

문제 스샷 말고 링크를 가져와

[익명(223.62)]

1번이 의미하는게 몬질 몰르겠자너

[ㅁㄴㅇㄹ(110.9)]

요기

[ㅁㄴㅇㄹ(110.9)]

https://www.acmicpc.net/problem/13459

[ㅁㄴㅇㄹ(110.9)]

지금 BFS로 가닥잡고 짜고있는데 큐 터질거같다

[익명(223.62)]

최대 4^10까지 가니까 터질거같은데

[익명(223.62)]

내생각엔 dfs가 더 나을거같다 깊이 10 까지만 가보고 나갈수도 있고 중간에 답나오면 바로 나와도되고

[ㅁㄴㅇㄹ(110.9)]

dfs로 짜려면 dfs(공위치값,방향,시도횟수) 이렇게 잡고 방향만 바꿔주면서 계속돌려?

[ㅁㄴㅇㄹ(110.9)]

어? 근데 4의10승 100만밖에 안되서 시간제한은 괜찮을거같은데 큐만 좀 가지치면 bfs도될거같지않냐

[익명(223.62)]

빨간공위치, 파란공위치, 횟수면 될거같은데

[익명(223.62)]

시간제한 말구 메모리 터질거같은데

[ㅁㄴㅇㄹ(110.9)]

그러면 dfs(빨공,파공,횟수){ for(i=0;i<4;i++) 빨공 파공을 상하좌우로 이동시킨 후 dfs(바뀐 빨공,바뀐파공, 횟수+1)}

[ㅁㄴㅇㄹ(110.9)]

이렇게 짜고 깊이 10 안넘게 기저조건을 if(횟수>10) return;

[ㅁㄴㅇㄹ(110.9)]

이렇게짜면 될거같아???

[익명(223.62)]

루프로 dx dy 구할수 있을라나

[익명(223.62)]

그건 머 알아서하고 대충 그런식

[ㅁㄴㅇㄹ(110.9)]

dfs보다 공을 아래로 쭉 미는걸 구현하는게 더 급하네

[ㅁㄴㅇㄹ(110.9)]

일단 해볼게 ㄳ

[익명(223.62)]

이동하는거 만들고 가지 좀만 치면 충분할거같다

[익명(223.62)]

시간이랑 메모리도 넉넉하네

[ㅇㄹㅇㅅㅇㅈ(64.140)]

pathfinding 문제 아니냐?

[ㅇㄹㅇㅅㅇㅈ(64.140)]

A* (a star) 알고리즘 찾아봐라

[아놔콘다(anwaconda)]

각 위치 Lk마다 그다음에 이동 가능한 위치는 총 4군데... 이중에서 1이미 방문한곳 2벽으로 막힌곳 3파란구슬위치 는 제외하고 재귀호출.... 로 하면 망함. 위 문제는 외길인경우 빨간 구슬로 파란 구슬을 밀면서 가는 경우를 고려해야할듯. 에를들어서 R 로 B를 위로 밀면서 이동하다 옆길 나오면 R만 우회전... 이런 경우

[아놔콘다(anwaconda)]

현재위치 Lk에서 이동가능한 4군데 위치 중 1) #이면 제외. 2)이미 밟은 길은 제외 3) B가 있는 경우 2가지로 나뉨 3-1) R과 B를 그쪽방향으로 이동시키고 재귀호출 3-2)B를 #처럼 피함.... 그러면 남는건 최적화인데 R이 출구와 반대로 멀어지는 경우 굳이 10번 다 가보지 않아도 되는 경우가 있음.

[아놔콘다(anwaconda)]

R과 O의 최단거리(맨해튼거리값) x와 현재 남은 이동횟수 y 를 비교해서 x >y 이면 이거는 더 가볼 필요 없음.길이 있어도 y번안에 O까지 못감.

[ㅇㄹㅇㅅㅇㅈ(64.140)]

링크 들어가서 읽어보니까 평범한 pathfinding은 아니구나.. 그래도 game state tree가 quadtree인건 변함이 없으니 비슷하게 해도 될듯