#문제 설명

백준, 2206 벽 부수고 이동하기

문제: https://www.acmicpc.net/problem/2206

#오답 풀이

시작점에서 도착점까지의 최단 거리는 BFS로 구한다. 문제는 어떤 벽을 부숴야 하는지이다. 내가 짠 알고리즘은 이러했다.

  1. 시작점에서 어떤 벽까지의 최단 거리 + 그 벽에서 도착점까지의 거리를 구하기 위해, BFS를 두 번 나누어 수행한다.
  2. 처음 BFS에서는 방문하지 않은 길을 탐색하면서, 벽을 만난다면 벽의 위치를 다른 큐에 담는다. visited에 거리를 담는다.
  3. 다음 BFS에서는 벽의 위치를 담은 큐를 가지고 BFS를 수행한다. 벽에서 시작한다는 건 이미 벽을 부쉈다는 것이라고 볼 수 있으므로, 벽을 만난다면 무시한다. 반면 저번에 방문한 적이 있는 위치여도 현재 루트로 가는 게 더 빠르다면, 다시 탐색할 수 있도록 현재 큐에 담는다.
  4. visited의 도착점에 저장된 거리를 출력한다.

코드가 좀 길어서 접어두겠다. 베리베리 스파게티 코드다.

더보기 
class Queue {
  length = 0;

  constructor(node = null) {
    this.head = node;
    this.tail = node;
  }

  createNode(data) {
    const node = {
      prev: null,
      next: null,
      data: data,
    };
    return node;
  }

  push(data) {
    const node = this.createNode(data);
    if (this.head === null) {
      this.head = node;
    } else {
      node.prev = this.tail;
      this.tail.next = node;
    }
    this.tail = node;
    this.length++;
  }

  shift() {
    if (this.head === null) return;

    const oldHead = this.head;
    this.head = oldHead.next; // assign new head
    oldHead.next = null;
    if (this.head) this.head.prev = null;

    this.length--;
    return oldHead.data;
  }
}

const fs = require('fs');
const [size, ...lines] = fs
  .readFileSync('/dev/stdin')
  .toString()
  .trim()
  .split('\n');

const [H, W] = size.split(' ').map(Number);
const map = lines.map((line) => [...line]);
const visited = Array.from({ length: H }).map(() =>
  Array.from({ length: W }).fill(-1),
);
solution();

function solution() {
  let firstQueue = new Queue(); // 벽 부수기 전, 탐색 노드를 담을 큐
  let secondQueue = new Queue(); // 벽 부순 후, 탐색 노드를 담을 큐

  // 시작 노드 설정
  firstQueue.push([0, 0]);
  visited[0][0] = 1;

  firstBFS(firstQueue, secondQueue);
  secondBFS(secondQueue);

  console.log(visited[H - 1][W - 1]);
}

function firstBFS(firstQueue, secondQueue) {
  const dr = [1, -1, 0, 0];
  const dc = [0, 0, 1, -1];

  while (firstQueue.length > 0) {
    const [r, c] = firstQueue.shift();
    if (r === H - 1 && c === W - 1) break; // 현 위치가 도착 지점인 경우 탈출

    for (let i = 0; i < 4; i++) {
      const nr = r + dr[i];
      const nc = c + dc[i];

      // 위치가 맵 밖이거나, 방문한 적 있는 위치인 경우 continue
      if (!isValidPosition(nr, nc) || visited[nr][nc] !== -1) continue;

      if (map[nr][nc] === '0') {
        firstQueue.push([nr, nc]);
        visited[nr][nc] = visited[r][c] + 1;
      } else if (map[nr][nc] === '1') {
        secondQueue.push([nr, nc]);
        visited[nr][nc] = visited[r][c] + 1;
      }
    }
  }
}

function secondBFS(queue) {
  const dr = [1, -1, 0, 0];
  const dc = [0, 0, 1, -1];

  while (queue.length > 0) {
    const [r, c] = queue.shift();
    if (r === H - 1 && c === W - 1) break;

    for (let i = 0; i < 4; i++) {
      const nr = r + dr[i];
      const nc = c + dc[i];

      // 위치가 맵 밖이거나, 벽이 있는 위치인 경우 continue
      if (!isValidPosition(nr, nc) || map[nr][nc] !== '0') continue;

      // 방문한 적 없는 위치이거나, 방문한 적이 있지만 지금 탐색한 길보다 오래 걸렸었다면
      if (visited[nr][nc] === -1 || visited[nr][nc] > visited[r][c] + 1) {
        queue.push([nr, nc]);
        visited[nr][nc] = visited[r][c] + 1;
      }
    }
  }
}

function isValidPosition(r, c) {
  return 0 <= r && r < H && 0 <= c && c < W;
}

질문 게시판에 있는 반례들은 다 해봤고, 모두 정답이었다. 하지만 메모리 초과가 났다.

큐에 중복된 값이 들어가는 것 때문이 아닐까 싶어, 중복 값이 있는지 확인하는 코드를 추가했는데 시간 초과가 났다.

BFS를 두 번 수행하는 것도 영향이 있을 것 같았다.

답을 맞추고 나니 그 외에도 많은 이슈들이 있을 거 같다.

될 것 같은데 안 되니까 계속 붙잡고 있게 돼서 결국에는 포기하고 답을 찾아봤다.

 

#정답 풀이

문제의 핵심은 "벽을 딱 한 번만 부술 수 있다"는 것이다. 현재 위치까지 벽을 부숴서 왔는지, 부수지 않고 왔는지 알아야 한다는 거다. 벽을 부순 적이 있다면 벽을 만났을 때 되돌아가야 하고, 벽을 부순 적이 없다면 벽을 만났을 때 부술 수 있다.

또 "최단 거리"를 구해야 한다는 것이다. 시작점부터 현재 위치까지의 거리를 어딘가 저장해야 한다는 거다. 또 도착점에 도착한 순간 탐색을 종료해야 한다(BFS 사용 시).

 

나는 BFS를 벽 부수기 전/후로 나누어 수행했다. 즉 벽 부순 여부는 이미 정해져있는 거였다. 하지만 탐색을 비효율적으로 해서(중복을 가능케 해서) 메모리/시간 초과가 났다.

중복을 허용하지 않으려면, BFS를 한 번만 수행해야 한다. 여러 번 수행할거면 방문하지 않은 노드 한정으로 탐색을 해야 한다.

 

BFS를 한 번만 수행하도록 바꾸면서, 벽 부순 여부를 따로 저장해야 했다. 이걸 visited에 저장했다. visited를 3차원으로 만들고(벽 부쉈는지 여부, row, column) 방문 여부를 값으로 담았다.기존에는 거리를 값으로 담았었는데, 그렇게 해도 된다. 근데 좀 복잡해지는 것 같아서 거리는 노드 데이터로 따로 저장했다.

 

코드는 다음과 같다.

class Node {
  constructor(data) {
    this.next = null;
    this.data = data;
  }
}

class Queue {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  push(...data) {
    const node = new Node(data);

    if (this.head === null) this.head = node;
    else this.tail.next = node;

    this.tail = node;
    this.length++;
  }

  shift() {
    if (this.head === null) return;

    const data = this.head.data;
    this.head = this.head.next;
    this.length--;
    return data;
  }
}

function solution() {
  const queue = new Queue();
  queue.push(0, 0, 1, 1); // row, col, distance, canBreak
  const answer = bfs(queue); // returned distance or -1
  console.log(answer);
}

function bfs(queue) {
  const dr = [1, -1, 0, 0];
  const dc = [0, 0, 1, -1];

  while (queue.length > 0) {
    const [r, c, d, canBreak] = queue.shift();
    if (r === H - 1 && c === W - 1) return d;

    for (let i = 0; i < 4; i++) {
      const nr = r + dr[i];
      const nc = c + dc[i];

      if (!isValidPosition(nr, nc) || visited[canBreak][nr][nc]) continue;
      
      if (map[nr][nc] === '0') {
        queue.push(nr, nc, d + 1, canBreak);
        visited[canBreak][nr][nc] = true;
      } else if (map[nr][nc] === '1' && canBreak) {
        queue.push(nr, nc, d + 1, 0); // canBreak = 0
        visited[0][nr][nc] = true;
      }
    }
  }
  return -1;
}

function isValidPosition(r, c) {
  return 0 <= r && r < H && 0 <= c && c < W;
}

const fs = require('fs');
const [size, ...lines] = fs
  .readFileSync('/dev/stdin')
  .toString()
  .trim()
  .split('\n');

const [H, W] = size.split(' ').map(Number);
const map = lines.map((line) => [...line]);

// visited[hasBreak][row][column]
const visited = Array.from({ length: 2 }).map(() =>
  Array.from({ length: H }).map(() => Array.from({ length: W }).fill(false)),
);
solution();

#정리

  • 알고리즘에 문제가 없어보이는데, 반례도 다 맞는데..! 그래도 안 된다면 겸손한 자세로 내 코드를 되돌아보자 ㅋㅋ. 틀리는 데에는 이유가 있을 테니까.
  • 문제 참 어려웠다. 처음에 보고 어떻게 풀어야 하는지 도저히 생각이 안 나서 미뤄놨었다. 나중에 아는 분이 시작점-벽 거리와 벽-도착점 거리를 더하는 아이디어를 알려주셔서 그나마 풀 수 있었다. (그래도 오답이었지만...)
  • 정답 보고 직접 코드 짜보니까 한 번에 맞았다. ㅎㅎ.. ㅜㅜ 나이스 힘들다 힘들어

저작자표시 비영리 변경금지 (새창열림)

'Algorithm' 카테고리의 다른 글

JS | 퍼즐 조각 채우기  (0) 2025.03.26
python | 유기농 배추  (0) 2023.07.30
python | 송아지 찾기  (0) 2023.07.24
js | 완주하지 못한 선수  (0) 2021.07.28

티스토리툴바