Baekjoon 2567번 색종이 - 2

문제

https://www.acmicpc.net/problem/2567

걸린 시간

-

풀이

TypeScript

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input';
const stdin = fs.readFileSync(filePath).toString().trim().split('\n').map((s: string) => s.trim());
const input = (() => {
  let line = 0;
  return () => stdin[line++];
})();

const n: number = parseInt(input());

const paper: Array<Array<number>> = Array.from(Array(100), () => Array(100).fill(0));
// 1 : 색종이
// 0 : 빈 곳
const visited: Array<Array<number>> = Array.from(Array(100), () => Array(100).fill(0));

for(let i = 0; i < n; i++){
  let [x, y] = input().split(' ').map(Number);
  for(let r = 99-y; r > 99-y-10; r--){
    for(let c = x; c < x+10; c++){
      paper[r][c] = 1;
    }
  }
}

const dy: number[] = [-1, 1, 0, 0];
const dx: number[] = [0, 0, -1, 1];

interface pair{
  y: number,
  x: number
}

const bfs: Function = (r: number, c: number) => {
  const q: pair[] = [{y: r, x: c}];
  visited[r][c] = 1;
  while(q.length){
    const size: number = q.length;
    for(let i = 0; i < size; i++){
      const y: number = q[0].y;
      const x: number = q[0].x;
      q.shift();
      let zero: number = 0;
      for(let j = 0; j < 4; j++){
        const ny: number = y+dy[j];
        const nx: number = x+dx[j];
        if(ny >= 0 && ny < 100 && nx >= 0 && nx < 100){
          if(paper[ny][nx] === 0) zero++;
          else{
            if(!visited[ny][nx]){
              visited[ny][nx] = 1; // 빈 공간을 미리 방문처리해버리면 접근할 수가 없다.
              q.push({y: ny, x: nx});
            }
          }
        }
        else zero++;
      }
      if(zero) paper[y][x] = zero+1;
    }
  }
}

for(let r = 0; r < 100; r++){
  for(let c = 0; c < 100; c++){
    if(paper[r][c] !== 0 && !visited[r][c]) bfs(r, c);
  }
}

let ans: number = 0;

for(let i = 0; i < 100; i++){
  const side: number = paper[i].filter(x => x === 2).length;
  const edge: number = paper[i].filter(x => x === 3).length * 2;
  ans += side;
  ans += edge;
}

console.log(ans);

문제를 읽고 좌표를 기준으로 색종이를 저장하다 보니 둘레를 가장자리 좌표의 개수로 잘못 이해하고 풀어 bfs 로 모든 가장자리 좌표를 표시한 후 개수를 세었다.

우연히?도 위 예제는 제대로 둘레를 구했을 때 와 결과값이 똑같았고 그래서 더 삽질을 했다.

둘레의 개념을 이해하고 변, 가장자리만 좌표에 표시한 뒤 중복되는 가장자리는 2배를 해 주어 결과값을 구했다.

(이 와중에도 잘못된 방문처리와. 인접한 대각선 좌표까지 처리하는 바람에 가장자리 좌표를 표시하는 작업도 많이 헤맴)