너비 우선 탐색(BFS) (2) - 아이템 줍기 / 퍼즐조각 채우기

아이템 줍기

캐릭터의 초기 위치와 아이템의 위치가 주어질 때, 다각형의 테두리를 따라 이동해야 하며 가장 짧은 거리를 구하는 문제

여러 직사각형으로 이루어진 다각형 테두리(둘레)를 따라 캐릭터가 아이템까지 이동한다.

풀이 전략

1. 좌표 확장 및 테두리 정의좌표를 2배 또는 2배 이상 확장하여 정밀도를 높인다. 이렇게 하면 테두리와 내부를 명확히 구분할 수 있다.
2. 맵 생성모든 직사각형 테두리와 내부 좌표를 계산하여 맵을 생성한다.
3. 테두리 경로 탐색테두리에 해당하는 좌표를 BFS(너비 우선 탐색)로 탐색하여 최단 경로를 구한다.
4. 최단 거리 계산BFS를 통해 캐릭터의 시작 위치에서 아이템 위치까지의 최단 거리를 계산한다.

알고리즘 풀이

function solution(rectangle, characterX, characterY, itemX, itemY) {
  // 좌표를 2배 확장하여 정밀도 증가
  const size = 102; // 50*2보다 약간 큰 크기
  const map = Array.from(Array(size), () => Array(size).fill(0));

  // 좌표 확장 및 테두리와 내부 채우기
  rectangle.forEach(([x1, y1, x2, y2]) => {
    x1 *= 2;
    y1 *= 2;
    x2 *= 2;
    y2 *= 2; // 좌표 확장
    for (let x = x1; x <= x2; x++) {
      for (let y = y1; y <= y2; y++) {
        if (x === x1 || x === x2 || y === y1 || y === y2) {
          if (map[x][y] !== 2) map[x][y] = 1; // 테두리
        } else {
          map[x][y] = 2; // 내부
        }
      }
    }
  });

  // BFS를 이용한 최단 경로 탐색
  const directions = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1]
  ]; // 상, 하, 좌, 우
  const queue = [[characterX * 2, characterY * 2, 0]]; // x, y, 거리
  const visited = Array.from(Array(size), () => Array(size).fill(false));
  visited[characterX * 2][characterY * 2] = true;

  while (queue.length > 0) {
    const [x, y, dist] = queue.shift();

    // 아이템 위치에 도달한 경우
    if (x === itemX * 2 && y === itemY * 2) {
      return dist / 2; // 확장된 좌표이므로 거리 원상 복구
    }

    for (const [dx, dy] of directions) {
      const nx = x + dx;
      const ny = y + dy;

      // 맵의 범위 안에 있고, 테두리이며 방문하지 않은 경우
      if (
        nx >= 0 &&
        ny >= 0 &&
        nx < size &&
        ny < size &&
        map[nx][ny] === 1 &&
        !visited[nx][ny]
      ) {
        visited[nx][ny] = true;
        queue.push([nx, ny, dist + 1]);
      }
    }
  }
}

시간 복잡도

1. 맵 생성 단계모든 직사각형의 좌표를 순회하며 테두리와 내부를 설정하므로 O(n×w×h) (직사각형 개수와 너비, 높이의 곱)
2. BFS 탐색 단계맵 전체의 테두리 좌표를 탐색하므로 최악의 경우 O(w×h) (테두리의 크기)

결론적으로, 시간 복잡도는 O(n×w×h)이다. 여기서 은n 직사각형의 개수, w와 h는 직사각형의 너비와 높이를 의미한다.

---

퍼즐 조각 채우기

주어진 게임 보드의 빈칸과 테이블의 퍼즐 조각을 적절히 맞춰 넣어 최대한 많은 칸을 채우는 문제

퍼즐 조각은 회전시킬 수 있지만 뒤집을 수는 없으며, 주어진 규칙에 맞게 조각을 게임 보드에 배치해야 한다.

풀이 전략

1. 게임 보드와 테이블의 블록 탐색:
   • BFS를 사용해 연결된 칸(빈칸 또는 퍼즐 조각)을 찾아 블록 리스트를 생성한다.
   • 블록의 좌표를 정규화하여(좌표를 기준점 (0, 0)으로 이동) 비교 가능하게 만든다.
2. 퍼즐 조각 회전:
   • 주어진 블록을 90도씩 회전하며 최대 4번의 회전을 수행해 모든 방향에서 매칭 가능한지 확인한다.
3. 퍼즐 배치:
   • 빈칸 리스트와 퍼즐 조각 리스트를 순회하며, 각 빈칸에 맞는 조각이 있는지 확인한다.
   • 매칭된 퍼즐 조각은 빈칸 리스트에서 제거하고, 조각의 칸 수를 결과값에 더한다.

알고리즘 풀이

function solution(tickets) {
  const graph = {};
  const result = [];

  // 그래프 생성: 각 출발지에 대해 가능한 도착지를 알파벳 순으로 정렬
  tickets.forEach(([from, to]) => {
    if (!graph[from]) graph[from] = [];
    graph[from].push(to);
  });

  for (const from in graph) {
    graph[from].sort(); // 알파벳 순 정렬
  }

  function dfs(node) {
    const destinations = graph[node];

    while (destinations && destinations.length > 0) {
      const next = destinations.shift(); // 사전순으로 탐색
      dfs(next);
    }

    result.push(node); // 역순으로 추가
  }

  dfs("ICN"); // 항상 "ICN"에서 출발
  return result.reverse(); // 역순을 뒤집어서 반환
}

시간 복잡도

1. BFS 탐색:
   • 각 셀에 대해 한 번만 방문하므로 O(n^2), n은 게임 보드 한 변의 길이
2. 블록 회전 및 매칭:
   • 각 블록당 최대 4번 회전, O(k⋅m), k는 블록의 크기, m은 빈칸/블록의 수
3. 전체 복잡도:
   • O(n^2+m⋅k⋅4)로, n≤50, m,k≤n^2