거리두기 확인하기

문제 접근

2차원 배열로 표현되는 평면에 대해서 정해진 규칙을 수행하는 문제입니다. 문제의 경우 파티션으로 막혀있지 않은 경우 맨해튼 거리가 2이내로 사람들이 떨어져 있는지 판단하는 문제입니다. 문제 조건은 다음과 같이 재 구성했습니다.
1. 사람이 있는 좌표 기준 동서남북 네 방향에 어떤 것이 있는지 탐색합니다.
2-1. 사람이 있다면, 0을 리턴합니다.
2-2. 빈 공간이라면 3번 으로 이동합니다.
2-3. 벽이 있다면 다른 방향으로 이동후 2-1 부터 다시 시작합니다.(벽이 있다면 벽이 있는 방향 맨해튼 거리 2 불가)
3. 다시 동서남북 네 방향에 어떤 것이 있는지 탐색합니다.
4. 사람이 2이상 있을 경우 0을 리턴합니다. (기본적으로 사람 1명은 있으므로)
5. 맨해튼 거리 2 이내에 사람들이 없을 경우 1을 리턴합니다.

문제 풀이

function solution(places) {
  const n = places[0].length
  const searchDir = (i, j, n) => {
    const arr = []
    if (j - 1 >= 0) {
      arr.push([i, j - 1])
    }
    if (j + 1 <= n - 1) {
      arr.push([i, j + 1])
    }
    if (i - 1 >= 0) {
      arr.push([i - 1, j])
    }
    if (i + 1 <= n - 1) {
      arr.push([i + 1, j])
    }
    return arr
  }
  const result = []
  places.forEach((place) => {
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        if (place[i][j] === 'P') {
          const arrToSearch = searchDir(i, j, n)
          for (let site of arrToSearch) {
            const [row, col] = site
            if (place[row][col] === 'P') {
              result.push(0)
              return
            } else if (place[row][col] === 'O') {
              const newArrToSearch = searchDir(row, col, n)
              let pNum = 0
              for (let newSite of newArrToSearch) {
                const [newRow, newCol] = newSite
                if (place[newRow][newCol] === 'P') {
                  pNum += 1
                  if (pNum > 1) {
                    result.push(0)
                    return
                  }
                }
              }
            }
          }
        }
      }
    }
    result.push(1)
  })
  return result
}

느낀 점

사실 그렇게 좋은 풀이라고 생각되지 않는다. 수 많은 for-loop와 if를 사용하는 바람에 가독성이 너무 떨어지고 특히

			  let pNum = 0
              for (let newSite of newArrToSearch) {
                const [newRow, newCol] = newSite
                if (place[newRow][newCol] === 'P') {
                  pNum += 1
                  if (pNum > 1) {
                    result.push(0)
                    return

이 부분에서는 이미 알고 있는 사람의 위치를 한 번 더 조사하여 효율성 측면에서 아쉬움이 남는다.

풀이 수정

결국 사용자 주위의 2차원 배열을 거리 2만큼 모든 방향에 대해 탐색하는 문제이므로 dfs를 사용하면 된다.
주의할 점은,

1. 2차원 배열을 깊은 복사할 때는 다음과 같은 방법이 통하지 않는다.

const arr = [[1],[2],[3]]
const arr2 = [...arr]

각 배열 요소를 하나씩 복사해야 한다.

const arr = [[1],[2],[3]]
const arr2 = []
arr.forEach(e => arr2.push([...e]))

2. dfs를 통해 탐색할 때, p를 발견했을 경우 for-loop를 중간에 break해야 하는데, 이 때 사용하는 변수는 전역 let 변수로 설정해 준다.

let isOkay
...
  const dfs = (level, node, visited, place) => {
  ...
          if (place[x + dx][y + dy] === 'P') {
            isOkay = 0
            return
...
  }
  places.forEach((place) => {
    isOkay = 1
    for (let row = 0; row < 5; row++) {
      for (let col = 0; col < 5; col++) {
 ...
          dfs(0, [row, col], newVisited, place)
          if (isOkay === 0) break
        }
      }
      if (isOkay === 0) break
    }
    answer.push(isOkay)
  })
  ...

새로운 풀이

function solution(places: string[][]) {
  const answer = []
  const directions = [
    [-1, 0],
    [1, 0],
    [0, 1],
    [0, -1],
  ]
  let isOkay
  const visited = new Array(5).fill(0).map((e) => new Array(5).fill(0))
  const dfs = (level, node, visited, place) => {
    if (level === 2) return
    else {
      const [x, y] = node
      directions.forEach((dir) => {
        const [dx, dy] = dir
        if (x + dx >= 0 && x + dx < 5 && y + dy >= 0 && y + dy < 5 && place[x + dx][y + dy] !== 'X' && visited[x + dx][y + dy] !== 1) {
          if (place[x + dx][y + dy] === 'P') {
            isOkay = 0
            return
          } else {
            const newVisited = []
            visited.forEach((row) => newVisited.push([...row]))
            newVisited[x + dx][y + dy] = 1
            dfs(level + 1, [x + dx, y + dy], newVisited, place)
          }
        }
      })
    }
  }
  places.forEach((place) => {
    isOkay = 1
    for (let row = 0; row < 5; row++) {
      for (let col = 0; col < 5; col++) {
        if (place[row][col] === 'P') {
          const newVisited = []
          visited.forEach((row) => newVisited.push([...row]))
          newVisited[row][col] = 1
          dfs(0, [row, col], newVisited, place)
          if (isOkay === 0) break
        }
      }
      if (isOkay === 0) break
    }
    answer.push(isOkay)
  })
  return answer
}