알고리즘 문제 풀어보기

무인도 여행

문제 설명

메리는 여름을 맞아 무인도로 여행을 가기 위해 지도를 보고 있습니다. 지도에는 바다와 무인도들에 대한 정보가 표시돼 있습니다. 지도는 1 x 1크기의 사각형들로 이루어진 직사각형 격자 형태이며, 격자의 각 칸에는 'X' 또는 1에서 9 사이의 자연수가 적혀있습니다. 지도의 'X'는 바다를 나타내며, 숫자는 무인도를 나타냅니다. 이때, 상, 하, 좌, 우로 연결되는 땅들은 하나의 무인도를 이룹니다. 지도의 각 칸에 적힌 숫자는 식량을 나타내는데, 상, 하, 좌, 우로 연결되는 칸에 적힌 숫자를 모두 합한 값은 해당 무인도에서 최대 며칠동안 머물 수 있는지를 나타냅니다. 어떤 섬으로 놀러 갈지 못 정한 메리는 우선 각 섬에서 최대 며칠씩 머물 수 있는지 알아본 후 놀러갈 섬을 결정하려 합니다.

지도를 나타내는 문자열 배열 maps가 매개변수로 주어질 때, 각 섬에서 최대 며칠씩 머무를 수 있는지 배열에 오름차순으로 담아 return 하는 solution 함수를 완성해주세요. 만약 지낼 수 있는 무인도가 없다면 -1을 배열에 담아 return 해주세요.

제한사항

3 ≤ maps의 길이 ≤ 100
3 ≤ maps[i]의 길이 ≤ 100
maps[i]는 'X' 또는 1 과 9 사이의 자연수로 이루어진 문자열입니다.
지도는 직사각형 형태입니다.

풀이 코드

function solution(maps) {
    const newMap = maps.map((n) => n.split(""));
  
    const dx = [1, 0, -1, 0];
    const dy = [0, 1, 0, -1];
  
    function DFS(x, y, num) {
      var sum = Number(num);
  
      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) {
          if (newMap[nx][ny] !== "X") {
            const next = newMap[nx][ny];
  
            newMap[nx][ny] = "X";
  
            sum += DFS(nx, ny, next);
          }
        }
      }
  
      return sum;
    }
  
    const answer = [];
  
    for (i = 0; i < newMap.length; i++) {
      for (j = 0; j < newMap[0].length; j++) {
        if (newMap[i][j] !== "X") {
          const start = newMap[i][j];
  
          newMap[i][j] = "X";
  
          answer.push(DFS(i, j, start));
        }
      }
    }
    return answer.length ? answer.sort((a, b) => a - b) : [-1];
  }

풀이 과정

우선 배열 안의 문자열을 배열로 반환해주고 상 하 좌 우 좌표를 미리 세팅해둔다.
DFS함수를 만들어 들어온 num을 string => 숫자로 변환해준다.
설정해둔 좌표 배열을 통해 상 하 좌 우를 탐색하고 지도를 벗어나지 않는지 판단한다.
만약 지도를 벗어나지 않고 X가 아닌 곳을 찾는다면 식량 수를 저장 후 그곳을 X로 변환하고 DFS를 통해 그 좌표부터 다시 탐색한다. 이후 그 리턴 값을 sum에 더해준다. 최종적으로는 다 더해진 sum을 반환한다.
이중 반복문을 통해 하나씩 살펴보고 X가 아닌 곳을 찾으면 일단 현재 수를 저장하고 그 곳을 X로 변환한다. DFS(x좌표, y좌표, 식량 수)함수를 실행하고 이 반환 값을 answer에 push한다. 만약 answer의 길이가 0 이라면 -1을 반환하고, 아니라면 오름차순으로 정렬 후 반환한다.

기술면접 문제 풀어보기

17. Stack과 Queue를 비교설명해주세요.

• 둘 다 데이터 구조의 한 종류이고 데이터를 순서대로 저장하지만 동작 방식에서 차이가 있음.

Stack

• 후입 선출(LIFO, Last In First Out) 구조.
  • 함수 호출 시 사용되는 재귀나 뒤로 가기 기능 등에 적합.
• 주로 사용하는 연산 : push(데이터 추가), pop(데이터 삭제)

Queue

• 선입 선출(FIFO, First In First Out) 구조.
  • 프린터 대기열이나 운영체제의 작업 스케줄링 등에 활용.
• 주로 사용하는 연산 : enqueue(데이터 추가), dequeue(데이터 삭제)

최종프로젝트

중간 MVP발표가 있었다. 다른 팀들은 진행상황이 좋아보였고 그랬기에 발표 자료에도 많은 내용이 담겨있었지만 우리 팀의 경우는 townSession과 dungeonSession으로 나뉘어지는데 townSession도 끝나지 않은 상태라서 ppt에 진행 상황에 관한 내용보단 기획적인 면을 설명하는데 중점을 두고 제작했다.
발표가 끝나고 피드백을 받았는데 아무래도 진도가 안나갔더라도 코드나 영상을 추가해서 진행상황을 보여주면 좋겠다고 말씀하시고 같은 내용으로 핸들러 설명할 때 코드 어떻게 작성했는지 보여주는 것 좋았다고 하셧다.
기획적인 내용이 주가 되다보니 로직을 소개할 때 글이 많이 들어갔는데 해당 부분을 지적해주시면서 처음 보는 사람도 내용 이해하기 쉽게 글을 많이 쓰는건 지양하는게 좋다고 하시고 만약 쓰게 된다면 띄워쓰기 같은 서식의 일관성을 지키라고 해주셧다.
이후 트러블 슈팅 부분에서 그렇게 해결하면 안된다 하시는부분을 말씀해주셧는데, 플레이어 특정이 되지 않는다고 패킷 자체에 Id를 담아서 사용하게 되면 클라이언트가 어떤 패킷을 보내도 서버는 믿게 되고 어떤 유저가 피해를 볼 수 있다고, 어뷰징 문제가 발생할 수 있다고 하셧다. 또, 소통이 잘 안되면 잘 소통해주면 좋겠다는 말씀도 하셧다.
다음 발표는 약 2주뒤에 최종 발표인데 이때는 피드백 받은 내용들을 지키면서, 해결안된 부분을 고치고 완성되는 모습을 보여주기위해 노력해야겠다.