로직

logic

• NxN크기의 영역에서 물의 높이는 0이상이다.
• 영역에서 지역의 높이는 2이상 100이하이다.
• 물에 잠기지 않는 "지역" 은 지역의 높이 > 물의 높이인 곳
• 물에 잠기지 않는 "영역" 은 상하좌우가 인접한 경우 하나로 친다.
• bfs로 방문여부(0==방문X,1==방문)와 잠김여부 (0==잠김,1==안잠김)로 방문하지 않았으면서 잠기지 않는 영역의 개수를 세준다.
• 방문 개수를 세줄 때 deque에 넣어 모두 방문할때까지 popleft를 해주기 파이썬 deque 대신 배열을 reverse해주고, pop해주고, 다시 reverse해주기
• 모든 물의 높이를 고려할 필요가 없으므로 최고 물 높이를 입력값을 받아올 때 구한다.
• 최고 물 높이는 가장 높은 지역의 높이 -1이다. (같으면 모든 지역이 잠기므로)

풀이

// https://www.acmicpc.net/problem/2468
interface Graph {
  items: Array<Array<number>>;
  count: number;
  max_num_arr: Array<number>;
  max_num: number;
  visited?: Array<Array<number>>;
  x_y_idx?: Array<number>;
  x?: number;
  y?: number;
}

const directions = [
  [0, 1],
  [0, -1],
  [1, 0],
  [-1, 0],
];

const dfs=(dq:Array<Array<number>>,a:Graph["items"],fld:Graph["items"],v:Graph["items"])=>{
    while (dq.length > 0) {
        const popLeft: Array<number> = dq[0];
        let x: number = popLeft[0];
        let y: number = popLeft[1];
        dq.splice(0,1);
        for (let k = 0; k < 4; k++) {
            let nx = x + directions[k][0];
            let ny = y + directions[k][1];
            if (0 <= nx && nx < a.length && ny >= 0 && ny < a.length) {
            if (fld[nx][ny] == 1 && v[nx][ny] === 0) {
                v[nx][ny] = 1;
                dq.push([nx, ny]);
            }
            }
        }
        }
}

//높이그래프 순회하면서 높이에 따른 잠긴 지역표시
const sunk = (area: Graph["items"], max_height: Graph["max_num"]) => {
  let h: number = max_height - 1;
  let flooded: Graph["items"];
  const ans_arr: Array<number> = [];
  while (h >= 0) {
    //잠김 = 0, 잠기지 않음 =1
    flooded = area.map((v) => {
      return v.map((itm) => {
        return itm > h ? 1 : 0;
      });
    });
    h--;
    const visited: Graph["visited"] = [...area].map((v) => [...v].fill(0));
    let cnt: number = 0;
    for (let i = 0; i < area.length; i++) {
      for (let j = 0; j < area.length; j++) {
        if (flooded[i][j] == 1 && visited[i][j] == 0) {
          let q: Array<Array<number>> = [];
          q.push([i, j]);
          dfs(q, area, flooded, visited);
          visited[i][j] = 1;
          cnt++;
        }
      }
    }
    ans_arr.push(cnt);
  }

  return Math.max(...ans_arr);
};
//input값들 받아오기 & 에러처리
const sol = () => {
  const n: string | null = prompt("지역의 개수 NxN개에서 N을 입력해주세요:");
  const N: Graph["count"] | null = n ? parseInt(n) : null;
  const max_arr: Graph["max_num_arr"] = [];
  const heights: Graph["items"] = [];
  let max_a: Graph["max_num"] = 1;
  if (n && N && !n.includes(" ")) {
    for (let i = 0; i < N; i++) {
      const h: string | null = prompt(`${i + 1}줄에서 지역의 높이`);
      h ? heights.push(h.split(" ").map((v) => parseInt(v))) : null;
      max_arr.push(Math.max(...heights[i]));
      if (heights[i].length !== N) {
        return console.log("구역의 높이 개수가 불일치 합니다.");
      }
    }
    if (heights.length === N && heights.map((v) => v.length == N)) {
      max_a = Math.max(...max_arr);
    } else {
      return console.log("구역의 높이 개수가 불일치 합니다.");
    }
  } else {
    console.log("지역의 개수가 부적합합니다.");
    return;
  }
  let count: number = 0;

  console.log(sunk(heights, max_a));
};

sol(); 6
8 9 5 2 7

output:5
--------
* test2
7
9 9 9 9 9 9 9
9 2 1 2 1 2 9
9 1 8 7 8 1 9
9 2 7 9 7 2 9
9 1 8 7 8 1 9
9 2 1 2 1 2 9
9 9 9 9 9 9 9

output:6

*/

😫Paid Extra Attention to..

• 입력값 : 잘못된 입력값 예외(에러)처리할 게 많아서 복잡했다.
• Array<Array<number>>식으로 중첩되는 타입 중복을 피하기 위해서 그래프 인터페이스를 만들어서 사용했다.
• 재귀로 돌렸을 때 탈출 조건을 제대로 잡지 못했다.
  • 처음에는 파이썬의 deque처럼 while(deque에 값이 있을때)라고 생각했는데, 자바스크립트 코드에서는 빈배열이 아니라 배열의 길이로 접근해야했다.
  • 두번째는 파이썬 내장 라이브러리 deque기능을 대체할 게 필요했다.
  • 처음에는 단순히 slice함수로 앞에 원본 배열을 복사해줘서 splice해줬던 값을 할당해주면 되지 않았나 싶었다. 근데 얕은 복사라서 그런지 삭제가 안됐다.
  • 대신 splice로 원본 배열 그자체에서 삭제하는 방식으로 구현했다.
  • 처음에는 reverse하고 pop하고 다시 reverse하는 식으로 했었는데, splice로 간단하게 처리 가능해서 수정했다.![]