성빈킴 블로그

백준 16929 Two Dots node.js

백준 16929 Two Dots node.js

2023-11-5

풀이방법

방금 전 노드가 아닌 노드중에 같은 문자인 곳으로 계속 이동하다가 방문한 적이 있는 노드를 만나면 사이클이 완성된다.

기본적으로 외부에서는 모든 노드를 한번씩 탐색하되 사이클을 찾은 경우 탐색을 중지한다.

결국 같은 인접한 노드중에 이전 노드가 아니고 같은 문자인 곳으로 계속 이동하다가 방문한 적이 있는 노드이면 사이클이 완성되는 것이다.

const [nm, ...boardLines] = `3 4 AAAA ABCA AADA` .trim() .split('\n'); const [n, m] = nm.split(' ').map(Number); const board = boardLines.map((line) => line.split('')); const visit = Array.from({ length: n }, () => Array(m).fill(false)); const ad = [ [-1, 0], [1, 0], [0, -1], [0, 1], ]; let haveCycle = false; function dfs(x, y, px, py, char) { if (visit[x][y]) { // 이미 방문한 노드면 사이클이므로 탐색 종료 haveCycle = true; return; } visit[x][y] = true; // 현재 노드 방문 표시 for (const [dx, dy] of ad) { // 인접 노드 탐색 const nx = x + dx; const ny = y + dy; // 게임 보드 내에 있고, 이전 노드가 아니며, 같은 문자를 가진 노드인 경우 탐색 계속 if (nx >= 0 && ny >= 0 && nx < n && ny < m) { if (!(nx === px && ny === py) && board[nx][ny] === char) { dfs(nx, ny, x, y, char); } } } } // 모든 노드에 대하여 DFS 탐색 시작 for (let i = 0; i < n; i++) { for (let j = 0; j < m && !haveCycle; j++) { // 사이클이 아직 발견되지 않았을 경우에만 계속 탐색 if (!visit[i][j]) { dfs(i, j, -1, -1, board[i][j]); } } } // 결과 출력 console.log(haveCycle ? 'Yes' : 'No'); // 사이클이 존재하면 'Yes', 그렇지 않으면 'No' 출력
백준 7562 나이트 node.js

백준 7562 나이트 node.js

백준 16947 서울지하철 2호선 node.js

백준 16947 서울지하철 2호선 node.js