링크

메이즈 러너

난이도

  • 골드3
    • 행렬회전, 그리고 완전탐색을 해도 되는지여부를 파악하는게 중점

문제요약

  • 참가자와 출구가 존재
    • 참가자는 10이하, 출구는 1, 미로는 10*10크기 이하
  • 참가자는 출구와 가까운 거리로 이동
    • 그저 출구와 제일 가까워지는 상하좌우로 간다.
    • 벽이 없을경우 이동
  • 출구와 참가자 하나를 포함한 가장 작은 정사각형 찾기
    • 정사각형을 시계방향으로 90도 이동
    • 이동시 벽은 내구도가 깍인다.
  • K번 반복 or 더이상 참가자 없을때까지 진행
  • 출력
    • 참가자가 이동한 횟수
    • 출구의 위치

접근

  • 기본 시뮬레이션
    • 전체적인 흐름은 어렵지 않으므로, 모듈화를 통해 구현을 시작

간단 알고리즘

  • 입력
    • 지도를 입력
      • 참가자는 +1해준다.
        • 동일한 좌표가 주어질수 있으니 해당좌표에 몇명있는지로 표현
      • 벽은 -1곱해준다.
        • 벽은 -로 표현한다.
      • 출구는 그 위치를 -10으로 설정
        • 내구도는 -9까지가능해서 남는 -10을 출구로 표현
  • 이동
    • 현재 사람이 있는지확인
      • 완탐으로가능
      • 아니면 사람수를 따로 변수로 해도 가능
    • 출구위치확인
      • 완탐으로 가능
      • 아니면 출구위치를 별도로 변수로 저장해도 가능
    • 조건을 잘 따져보자
      • 거리계산은 abs(r-exit.r)+abs(c-exit.c)같이 출구까지의 거리를 확인
      • 중요한점 = 현재위치보다 가까워지는 방향으로 가야한다.
        • 그러면? 현재위치를 미리 저장하고 4방향(상, 하, 좌,우)를 비교해서 가장 짧은 방향으로 이동한다.
    • 상->하->좌->우 순으로 반복한다.
      • 경계밖으로 간경우 넘기기
      • 만약 도착한 경우
        • 해당 위치의 참가자들을 이동한다
          • 이동횟수 +
      • 벽인경우
        • 이동못한다.
      • 0이상인경우
        • 참가자가있거나, 빈곳인경우
        • 해당 좌표로 참가자수만큼 + 해준다.
          • 기존에 해당 위치에 참가자가 이동했을수도 있으니 +를 해준다.
  • 회전
    • 시계방향으로 회전을 해야한다.
      • 참고
      • map[j][h-1-i] = map[i][j]를 통해 가능
    • 다른점은 행렬 전체가 아니라, 행렬의 일부분을 돌려야한다.
      • 행렬의 돌리는 일부를 따로 작은 행렬로 복사하여 진행한다.

후기

  • 이동조건과 행렬의 회전에서 고민을 많이했다.
    • 이동시 최단거리를 구할때의 기준을 현재 위치를 해야 하는점이 중요
    • 그저 4방향에서 최소로 한다면? 벽이 없는 최소거리로 가려고 한다.
  • 행렬회전
    • 모르고풀면 오래걸리지만, 공식만 알면 바로 해결되는 기출문제