백준 1388 - 바닥장식 (DFS) JS

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

// 입력
4 4
|--|
|--|
|--|
|--|

// 출력
6

문제에 제시된 예제를 사용하기에는 너무 단순하거나 오히려 길고 복잡하기에, 해당 블로그에서는 원활한 설명을 위해 예제를 만들었다.

문제에서 말했던 것처럼 연결된 막대기는 하나의 막대로 보기 때문에 

좌우측 4개로 이어진 막대기 각각 하나씩, 가운데 2개로 이어진 막대 4개. 즉 총 6(2+4)개가 되는 것이다.

 

해당 문제를 풀이는, 특정한 점에서부터 막대의 시작과 끝을 처리한 뒤 이를 하나의 막대로 취급하기 위해  DFS 알고리즘으로 구현하였다.

2023.06.01 - [개발/algorithm] - 프로그래머스 - Lv.2 타겟넘버 / 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS) 구현 방식 비교

DFS를 구현할 경우 위 제시한 예제는 다음과 같은 순서로 처리된다고 볼 수 있다.

1  5  6  7
2 11 12  8
3 13 14  9
4 15 16 10

// [0,0] 좌표 시작 시 왼쪽 막대 처리 ([0,0] ~ [3,0] 까지)
// [1,1] 좌표 시작 시 가운데 첫번째 막대 처리 ([1,1] ~ [1,2] 까지)
// 중략

 

전체 소스코드

const fs = require('fs')
const input = fs.readFileSync(process.platform === "linux" ? "/dev/stdin":"입력.txt")
  .toString().trim().split('\n')

function solution(data) {
  // 전체 범위 빼놓기
  const [Y,X] = data.shift().split(' ').map(Number)
  // 방문한 곳을 기록하기 위한 배열
  const visited = Array.from({length : Y}, ()=> {
    return Array.from({length : X}, ()=> false)
  })

  // 해당 좌표가 유효한 좌표인지 확인하는 함수
  const verify = (x,y) => {
    return X > x && x >= 0 && Y > y && y >= 0
  }
  
  // DFS 함수 / 좌표값과 해당 좌표의 막대가 어느 방향인지 전달
  const DFS = (x,y,stick) => {
    // 해당 좌표 방문 처리
    visited[y][x] = true
    // 좌표의 막대가 '-'이면 가로로, '|'이면 세로로 다음 방향 지정
    const direction = stick === '-' ? [1,0] : [0,1]

    // 막대와 맞는 다음 방향 좌표구하기
    const [dx,dy] = direction
    const [nx,ny] = [x + dx, y + dy]
	
    // '다음 진행할 좌표'가 유효하고, 방문한 적 없으며, 현재 좌표와 막대 모양이 같다면 DFS 함수 재귀 실행
    if(verify(nx,ny) && !visited[ny][nx] && data[ny][nx] === stick) {
      DFS(nx,ny,stick)
    }
  }

  let result = 0
  for(let i = 0 ; i < Y ; i ++) {
    for(let j = 0 ; j < X ; j ++) {
    // 방문하지 않은 곳에서 DFS 함수 실행
      if(!visited[i][j]) {
        DFS(j,i,data[i][j])
        // 로직이 끝남 => 즉 한 가지 막대의 연산이 종료될 시 막대 하나를 결괏값에 추가
        result ++
      }
    } 
  }
  console.log(result)
}

solution(input)

진행할 방향이 오른쪽과 아래쪽 밖에 없으니, 백준에서 다른 DFS문제들보다 난이도는 낮은 듯하나 풀이 과정은 크게 다르지 않다.