djm03178   2년 전

  1. 가중치가 없는 최단 경로는 무조건 BFS입니다. 왜 DFS가 안 될까요? 그 이유는 당연하게도, 특정 칸에 처음 도달했을 때까지의 경로의 길이가 다른 경로를 통해 도달한 길이보다 짧다는 보장이 전혀 없기 때문입니다. 아직까지 이 사실을 모르고 계셨다면, 이 문제는 아직 풀기에 너무 어렵습니다. 더 기본적인 BFS 문제들 (10https://www.acmicpc.net/proble... 등) 을 먼저 풀어보세요.
  2. 모든 칸을 전부 0으로 하나씩 바꾸어보고 BFS를 돌리는 것을 반복해서는 통과될 수 없습니다. 대부분의 알고리즘 문제가 그렇듯이, 풀이를 짜기 전에 반드시 해야 하는 것 중 하나는 시간 복잡도를 생각하는 것입니다. 시간 복잡도 계산, 전혀 어렵지 않습니다. 벽이 최대 O(NM)개 있는 맵에서, 벽을 하나 부술 때마다 O(NM)개의 칸을 탐색해야 하죠? 그러니 O((NM)^2)입니다. 이 수는 우리가 대충 1초에 돌 수 있다고 보는 단위인 1억을 10000배나 뛰어넘는 1조입니다. 절대 통과될 수 없겠죠?
  3. 칸마다 방문 체크 하나씩만 하는 방법으로는 풀 수 없습니다. 어떤 칸에 도달했을 때 나는 "아직 벽을 부술 수 있는 상태"일 수도 있고, "더 이상 벽을 부술 수 없는 상태"일 수도 있습니다. 큐에 그 상태를 넣은 것만으로 되는 것이 아닙니다. 당장 이 지점까지 어떻게든 최단으로 오는 길만 구했다고 해서, 그 이후의 여정도 최적으로 만들 수 있는 건 아닙니다. 구체적인 예시가 필요한가요?
    1. 현재 칸까지 벽을 안 부수고 최단으로 올 수 있었다고 가정해봅시다. 현재 지점에서 목표 지점까지 가는 데에, 벽을 한 개 부수고 가는 것이 안 부수고 가는 것보다 최적이 나온다고 해봅시다. 그렇다면 지금 내가 벽을 더 부술 수 있는 상태라는 사실을 알고 있어야만 되겠죠?
    2. 벽을 안 부수고도 현재 칸까지 도달이 가능하지만, 벽을 부수고 오는 것이 더 짧다고 가정해봅시다. 현재 지점에서 목표 지점까지 가려면 무조건 벽을 한 개 부숴야만 된다고 해봅시다. 비록 현재 칸까지는 벽을 부수고 오는 것이 최적이었지만, 이 상태로는 끝에 아예 도달을 못 하죠? 현재 칸까지는 더 멀더라도 벽을 안 부수고 와야, 끝에 도달이 가능하죠.
  4. (스포일러) 그래서 이 문제에서는 BFS에 대해 새로운 테크닉을 요구합니다. 단순히 좌표만을 큐에 넣어 탐색하는 방식을 넘어, "현재 상태" 자체를 큐에 넣어서 문제를 풀어야 합니다. 즉, 어떤 좌표에 있는가 뿐만 아니라, "여기까지 오면서 벽을 부순 적이 있는가" 여부를 함께 큐에 저장해서 탐색하고, 각각을 별개로 방문 체크해줘야 하는 문제입니다. visited[x][y]가 아니라, visited[x][y][벽을 부순 적이 있는가?] 가 되어야 합니다.
  5. 이 문제에서는 같은 칸에 방문하는 경우 벽을 안 부순 것이 더 유리하기 때문에 벽을 부쉈는지 여부를 방문 배열에 기록하여 부순 횟수가 더 적을 때만 방문하는 방법도 됩니다. 그러나 이는 문제의 특성 때문에 이 문제에서만 통하는 그리디이므로 다른 문제에도 함부로 사용해서는 안 됩니다.

skaduddn   1년 전

덕분에 풀었습니다

감사합니다!

minjoonist   3달 전

5번에서 부순 휫수가 더 적을 때만 방문하는 방법은 어떤 식으로 되는 건가요?

djm03178   3달 전

어떤 칸에 벽을 안 부순 상태로 도달하려고 하는데 이미 이전에 벽을 부순 상태로 도달한 적이 있었다면 그대로 방문해도 된다는 뜻입니다.

minjoonist   3달 전

만약 벽을 부순 상태로 어떤 칸에 도달했는데 벽을 부수지 않고 그 칸에 갈 수 있다면 그대로 간다는 말인가요?

djm03178   3달 전

네.

minjoonist   3달 전

아하 그렇군요

매번 계시판에서 많은 도움 받고 있습니다 감사합니다!

kssrcn   3달 전

visited[x][y][벽을 방문한적이 있는가?] 이런 방법을 쓰면 시간복잡도가 왜 O(NxM)이 나오는지 궁금합니다 ㅠㅠ

기존의 BFS는 visited[x][y]를 확인하면서 방문한적이 있으면 아예 그쪽으로 이동안해서 정확히 NxM만큼 확인하는걸 알수있으나

이 문제 같은 경우에는 visited[x][y][벽을 방문한적이 있는가?]를 갱신하는 방법으로 진행을 하기때문에 NxM보다 많이 확인하지 않나요?? 

djm03178   3달 전

그것이 각 칸에 대해 정확히 2개의 상태만을 만들기 때문에 시간 복잡도를 그대로 O(NM)이라고 쓸 수 있습니다. 시간 복잡도는 변수에 곱해지거나 더해진 상수는 무시하거나 변경하더라도 문제가 없기 때문입니다.

kssrcn   3달 전

감사합니다 이해되었습니다!

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