[DFS] 프로그래머스 '무인도 여행' - js

1. 문제

https://school.programmers.co.kr/learn/courses/30/lessons/154540#qna

프로그래머스

2. 구현

처음 푼 코드) 부분 정답

2차원 배열을 만들어주고 값이 X가 아니면 1을 넣어준 뒤, 상하좌우 요소 중 값이 1인게 하나라도 있으면 기존 값에 더해주고 없으면 이전 합을 더하고 temp에 새로운 값을 넣어주는 식으로 짰는데 부분 정답이 나왔다 ㅠㅠ

반례라도 있으면 문제를 파악하기 더 쉬울텐데, 어떤 부분이 틀렸는지 이해가 안된다 ㅠㅠ 

복기하다 보니 내 풀이가 왜 틀렸는지 이해가 된다. 중복값에 대한 처리를 안해준 것이 문제 인 듯 하다. 상하좌우 섬이 x가 아니라면 값을 무작정 더해줬으니 분명 중복으로 더해진 값이 있었을 것이다. 좌표문제는 더더욱 dfs를 사용해야겠다고 느꼈다.

function solution(maps) {
    let answer = [];
    let box = Array.from({length : maps.length+2}, () => new Array(maps[0].length+2).fill(0));
    let temp = 0;
    for(let i=0;i<maps.length;i++){
        for(let j=0;j<maps[i].length;j++){
            if(maps[i][j] !== "X") box[i+1][j+1] = 1;
        }
    }
    
    for(let i=0;i<maps.length;i++){
        let row = maps[i].split("");
        
        for(let j=0;j<row.length;j++){
            if(row[j] !== "X"){    
                if(box[i+1][j] || box[i+1][j+2] || box[i+2][j+1] || box[i][j+1] ) {
                    temp += +row[j];
                }
                else{
                    if(temp > 0) answer.push(temp);
                    temp = +row[j];
                }
            }
        }
    }
    temp !== 0 ? answer.push(temp) : null;
    
    return temp ? answer.sort((a,b) => a-b) : [-1];
}

정답)

아 좌표 문제... 비슷한 문제를 저번에 DFS/BFS 문제 섹션에서 본 것 같다. 좌표 문제는 한 번 익숙해지면 쉬울 것 같은데..

좌표 관련한 것 나오면 DFS..기억하자

function solution(maps) {
  const newMap = maps.map((n) => n.split("")); // 배열 안 문자열을 배열로 변환해준다.
  // 상 하 좌 우 좌표를 미리 세팅
  const dx = [1, 0, -1, 0];
  const dy = [0, 1, 0, -1];
  const answer = [];

  function dfs(x, y, cnt) {
    let sum = + cnt; // 요소가 문자이므로 숫자로 변환

    // 설정해둔 좌표 배열을 통해 상 하 좌 우를 탐색
    for (let i = 0; i < 4; i++) {
      const nx = x + dx[i];
      const ny = y + dy[i];
      // 현재 탐색 중인 좌표가 지도를 벗어나지 않는지 판단
      if (nx >= 0 && ny >= 0 && nx < newMap.length && ny < newMap[0].length) {
        // 지도를 벗어나지 않고 "X"가 아닌 곳을 찾는다면
        if (newMap[nx][ny] !== "X") {
          // 식량 수 저장
          const next = newMap[nx][ny];
          // "X"로 변환
          newMap[nx][ny] = "X";
          // dfs를 통해 리턴 값을 하나하나 sum에 더함
          sum += dfs(nx, ny, next);
        }
      }
    }

    return sum; // 최종 sum return(서로 연결된 하나의 무인도의 식량 합)
  }

  for (let i = 0; i < newMap.length; i++) {
    for (let j = 0; j < newMap[0].length; j++) {
      // "X"가 아닌 곳을 찾게된다면
      if (newMap[i][j] !== "X") {
        // 현재 식량 수 저장
        const start = newMap[i][j];
        // 현재 탐색 중인 요소를 X로 변환(한번 방문한 곳은 다시 방문하지 않기 위해)
        newMap[i][j] = "X";
        // dfs(x좌표, y좌표, 식량 수)를 실행하고 반환 값을 answer에 push
        answer.push(dfs(i, j, start));
      }
    }
  }

  // 만약 answer의 길이가 0이라면 [-1]을 리턴한다.
  // 아니라면 오름차순으로 정렬 후 리턴해준다.
  return answer.length ? answer.sort((a, b) => a - b) : [-1];
}

 

이해에 참고한 블로그)

https://leejams.github.io/%EB%AC%B4%EC%9D%B8%EB%8F%84%EC%97%AC%ED%96%89/

[프로그래머스] 무인도 여행 - JavaScript | LeeJam

 

복기

6/29