알고리즘 문제 풀이(프로그래머스 - 무인도 여행)

프로그래머스 LEVEL 2(무인도 여행)

• 사용 언어 : javascript

• 해결 날짜 : 2023-04-22

• 해결 방법 :

  • bfs를 활용하여 문제 해결
    • 주어진 maps 2차원 배열로 변경, 무인도 부분 q1에 push()
    • q1을 돌며 각 원소마다 bfs 적용

• 회고 :

  • 처음에 maps를 돌며 무인도인 부분을 큐에 넣고, 움직일 수 없을 때 index를 늘려주는 방식으로 문제를 해결하려 했다.
  • 문제에서 주어진 테스트 케이스는 모두 통과했으나, 제출 테스트 케이스는 대부분 실패했기에 로직에서 문제점이 있다고 생각했다.

  • 이는 현재와 다음이 이어져 있지 않더라도 index를 증가시키지 않기에 발생한 문제점이었다.

    function solution(maps) {
      const answer = [];
      const q = [];
      const moves = [
        [1, 0],
        [0, 1],
        [-1, 0],
        [0, -1],
      ];
    
      maps = maps.map((map, i) =>
        map.split('').map((v, j) => {
          if (v === 'X') return 0;
          q.push([i, j]);
          return parseInt(v, 10);
        }),
      );
    
      const maxWidth = maps[0].length,
        maxHeight = maps.length;
    
      if (!q.length) return [-1];
    
      let idx = 0;
    
      while (q.length) {
        const [x, y] = q.shift();
        const food = Math.abs(maps[x][y]);
        maps[x][y] = 0;
    
        if (food) {
          answer[idx] = (answer[idx] || 0) + food;
          let canMove = false;
    
          moves.forEach((move) => {
            const [nextX, nextY] = [x + move[0], y + move[1]];
    
            if (nextX < 0 || nextY < 0 || nextY >= maxWidth || nextX >= maxHeight) {
              return;
            }
    
            if (maps[nextX][nextY]) {
              maps[nextX][nextY] = -maps[nextX][nextY];
              canMove = true;
            }
          });
    
          if (!canMove) {
            idx++;
          }
        }
      }
    
      return answer.sort((a, b) => a - b);
    }
    

  • 따라서 움직일 수 없을 때만 index를 증가시키는 방식이 아닌 서로 이어진 무인도인지 체크하는 다른 로직이 필요했다.

  • 생각한 방법은 큐를 두 개 만들어 첫 큐의 원소마다 bfs를 적용하는 방법이었고, 모든 테스트 케이스에 통과할 수 있었다.

    

  • 풀고 나니 간단해 보이는데 생각보다 오래 걸린 케이스… 더 쉬운 방법이 있을 것 같다.

• 코드

  function solution(maps) {
    const answer = [];
    const q1 = [];
    const moves = [
      [1, 0],
      [0, 1],
      [-1, 0],
      [0, -1],
    ];
  
    maps = maps.map((map, i) =>
      map.split('').map((v, j) => {
        if (v === 'X') return 0;
        q1.push([i, j]);
        return parseInt(v, 10);
      }),
    );
  
    const maxWidth = maps[0].length,
      maxHeight = maps.length;
    const visited = Array.from({ length: maxHeight }, () =>
      Array.from({ length: maxWidth }, () => false),
    );
  
    if (!q1.length) return [-1];
  
    while (q1.length) {
      const start = q1.shift();
      let foods = 0;
  
      if (visited[start[0]][start[1]]) {
        continue;
      }
  
      const q2 = [start];
  
      while (q2.length) {
        const [x, y] = q2.shift();
        if (visited[x][y]) continue;
  
        foods += maps[x][y];
        visited[x][y] = true;
  
        moves.forEach((move) => {
          const [nextX, nextY] = [x + move[0], y + move[1]];
  
          if (nextX < 0 || nextY < 0 || nextY >= maxWidth || nextX >= maxHeight) {
            return;
          }
  
          if (maps[nextX][nextY] && !visited[nextX][nextY]) {
            q2.push([nextX, nextY]);
          }
        });
      }
  
      answer.push(foods);
    }
  
    return answer.sort((a, b) => a - b);
  }
  

• 출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges