[백준] 16919. Two Dots 풀이 (Python, JavaScript)

16929번: Two Dots

16919. Two Dots

접근한 방법

DFS로 완전탐색합니다. 사이클을 확인하는 방법은 시작 점을 다시 되돌아올 경우이므로 이차원 배열로 모든 정점을 DFS로 탐색해서 탐색 경로가 4회 이상이면서 사이클이 만들어지는 경우를 찾습니다.

 

Python

import sys
sys.stdin = open("input.txt", "r") # 제거
input = sys.stdin.readline

n, m = map(int, input().split())
visited = [[0] * m for _ in range(n)]
arr = [list(input().rstrip()) for _ in range(n)]
result = 0
def dfs(r, c, sr, sc, s, cnt):
    global result
    for d in ((-1, 0), (1, 0), (0, -1), (0, 1)): # 상하좌우 탐색
        nr, nc = r + d[0], c + d[1]
        if cnt >= 4 and [nr, nc] == [sr, sc]: # 4회 진입 & 시작점이 탐색 대상인 경우
            result = 1
            return
        if nr < 0 or nc < 0 or nr >= n or nc >= m: # 범위를 벗어난 경우
            continue
        if not visited[nr][nc] and arr[nr][nc] == s: # 방문하지 않았고 같은 문자인 경우
            visited[nr][nc] = 1
            dfs(nr, nc, sr, sc, s, cnt + 1)
            visited[nr][nc] = 0

for i in range(n):
    for j in range(m):
        if result:
            break
        visited[i][j] = 1
        dfs(i, j, i, j, arr[i][j], 1)
        visited[i][j] = 0
print("Yes" if result else "No")

JavaScript

function solution(n, m, arr) {
  let result = 0;
  const visited = Array.from({ length: n }, () => Array(m).fill(0));
  const dfs = (r, c, sr, sc, s, cnt) => {
    for (const d of [
      [-1, 0],
      [1, 0],
      [0, -1],
      [0, 1],
    ]) {
      const [nr, nc] = [r + d[0], c + d[1]];
      if (cnt >= 4 && nr == sr && nc == sc) return (result = 1);
      if (nr < 0 || nc < 0 || nr >= n || nc >= m) continue;
      if (!visited[nr][nc] && arr[nr][nc] === s) {
        visited[nr][nc] = 1;
        dfs(nr, nc, sr, sc, s, cnt + 1);
        visited[nr][nc] = 0;
      }
    }
  };
  for (let i = 0; i < n; i += 1) {
    for (let j = 0; j < m; j += 1) {
      if (result) return "Yes";
      visited[i][j] = 1;
      dfs(i, j, i, j, arr[i][j], 1);
      visited[i][j] = 0;
    }
  }
  return "No";
}

solution(3, 4, [
  ["A", "A", "A", "A"],
  ["A", "B", "C", "A"],
  ["A", "A", "A", "A"],
])