[13460] 구슬 탈출 2

  • tags: 구현, 그래프 이론, 그래프 탐색, 너비 우선 탐색, 시뮬레이션, 삼성

  • lev: g1

  • Python3 (code1.py)
    • 220412
    • 1:57:19 .47
    • 시도: 1번 (실패)
  • Python3 (code2.py)
    • 220413
    • 1:17:26 .67
    • 시도: 4번 (실패)
  • Python3 (code3.py)
    • 229422
    • 1:45:55 .37
    • 시도: 1번

메모

  • 구현과 트리 탐색이 조합된 괴랄한 문제
    • 구현의 경우, 공이 겹치는 경우, 빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패이다. 조건 성립.
    • 구현 문제의 경우, 구현 조건을 잘 보이는 곳에 써두자!!
  • code1.py
    • 최소값을 찾아야 하므로 BFS로 풀어야 한다…ㅠㅜ
    • code1.py -> DFS 풀이 / 시간초과
  • code2.py
    • BFS로 풀긴 풀었으나.. 각 노드 상태저장을 보드판 그대로를 deepcopy해서 풀음
    • 또 시간초과…
    • 보드판 전체가 아닌, 공의 위치만을 고려해서 풀어내는 방법을 사용해야 할 듯!
    • 위로 움직였으면, 다음 턴에 아래로 움직일 필요없음 / 오른쪽으로 움직였으면 다음 턴에 왼쪽으로 갈 이유 없음
      • 추가해도 시간초과…
  • code3.py
    • 위치만 큐에 넣어서 해결
    • 빼먹은 조건 찾느라 시간이 많이 소모되었다
      • 풀기 전에 반드시 어떻게 짤지를 조건과 함께 손으로 써보자
    • 풀이 중에 move(), solve() 패턴으로 해결한 사람이 많던데 나중에 확인해볼것

참고

  • import copy
aa = copy.deepcopy(target)



Link