[ 프로그래머스 ] 거리두기 확인하기 - python

 

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/81302

코딩테스트 연습 - 거리두기 확인하기

 

문제 요약

- 멘해튼 거리 : |y1 - y2| + |x1 - x2|

 

- 어떤 대기실에 있는 사람A가 있는 칸에서 출발하여, 인접한 칸에 대해 상하좌우로 움직이면서 사람B가 있는 칸까지 간다.

- 파티션이 있는 칸은 갈 수 없을 때, 사람 B까지 도달하는 최단거리를 구한다.

- 최단거리가 2 이하이면 거리두기를 지켰다고 할 수 없다.

 

 

 

 

 

코드

d = ((0, 1), (1, 0), (-1, 0), (0, -1))
SIZE = 5

def make_maps(place):
  arr = []
  men = []
  for i, str in enumerate(place):
    for j, char in enumerate(str):
      if char == 'P': men.append((i, j))

    arr.append(list(str))
  return arr, men

def isin(y, x):
  if -1 < y < SIZE and -1 < x < SIZE: return True
  return False

def bfs(arr, sy, sx):
  q = deque()
  q.append((sy, sx))
  table = [[-1 for _ in range(SIZE)] for _ in range(SIZE)]
  table[sy][sx] = 0

  while q:
    y, x = q.popleft()

    for dy, dx in d:
      ny = y + dy
      nx = x + dx

      if not isin(ny, nx): continue
      if arr[ny][nx] != 'X' and table[ny][nx] == -1:
        table[ny][nx] = table[y][x] + 1
        q.append((ny, nx))
  return table


def solution(places):
  answer = []
  for place in places:
    arr, men = make_maps(place)
    ok = True

    for man in men:
      table = bfs(arr, man[0], man[1])
      for other_man in men:
        if man != other_man:
          y = other_man[0]
          x = other_man[1]

          if -1 < table[y][x] <= 2:
            ok = False
            break

      if not ok: break

    if ok: answer.append(1)
    else: answer.append(0)
  print(answer)
  return answer

solution([["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"],
          ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"],
          ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"],
          ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"],
          ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]])