백준 16929 Two Dots

문제

제한 사항

입출력 예

풀이

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const solution = (input) => {
  let flag = 0;
  const [n, m] = input.shift().split(' ').map(Number);
  const table = input.map((e) => e.split(''));
  const visited = Array.from(Array(n), () => Array(m).fill(0)); // 방문 확인
  const dx = [-1, 0, 1, 0];
  const dy = [0, 1, 0, -1];

  const dfs = (x, y, cnt) => {
    if (flag) return;

    for (let i = 0; i < dx.length; i++) {
      const [nx, ny] = [x + dx[i], y + dy[i]];
      if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue; // 테이블을 벗어나니까
      if (table[nx][ny] !== table[start.x][start.y]) continue; //cnt가 4 이전엔 시작점으로 돌아가선 안된다. 사이클이 안되니까
      if (!visited[nx][ny]) {
        visited[nx][ny] = 1;
        dfs(nx, ny, cnt + 1);
        visited[nx][ny] = 0;
      } else if (cnt >= 4 && nx === start.x && ny === start.y) {
        flag = 1;
        return;
      }
    }
  };

  let start;
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      start = { x: i, y: j };
      visited[i][j] = 1;
      dfs(i, j, 1);
      visited[i][j] = 0;
      if (flag) break;
    }
  }

  return flag ? 'Yes' : 'No';
};

console.log(solution(input));

• 모든 점은 시작 점이 될 수 있다.
• 내부 dfs를 돌면서 시작점과 같은 알파벳이고 방문하지 않은곳은 방문하고 그렇지 않은 곳은 지나친다.
• cnt가 4이상(최소 사각형)에 다음점이 시작점과 같아지는 순간이 오면 flag에 1을 할당해 리턴 조건을 만족 시켜준다.
• 중요한 포인트는 모든 점이 시작점이 될 수 있는 것. 브루트포스를 하듯 모든 점을 방문하게 해야한다.