[프로그래머스] 거리두기 확인하기 / Python / 2021 카카오 채용연계형 인턴십

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

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

---

Solution

from collections import deque

dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]

def bfs(place, person):
    visited = [[False] * 5 for _ in range(5)]
    count = 0
    q = deque()
    q.append(person)
    while q:
        for _ in range(len(q)):
            y, x = q.popleft()
            visited[y][x] = True
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if nx < 0 or ny < 0 or nx >= 5 or ny >= 5 or visited[ny][nx]:
                    continue
                if place[ny][nx] == 'P':
                    return False
                elif place[ny][nx] == 'X':
                    continue
                else:
                    q.append((ny, nx))
                    
        count += 1
        if count == 2 or not q:
            return True

def solution(places):
    ans = []
    for place in places:
        people = deque()
        for i in range(5):
            for j in range(5):
                if place[i][j] == 'P':
                    people.append((i, j))
                    
        if len(people) == 0:
            ans.append(1)
            continue
        
        flag = True
        for person in people:
            if not bfs(place, person):
                flag = False
                break
        
        if not flag:
            ans.append(0)
        else:
            ans.append(1)
        
    return ans

 

1. 대기실은 5개이며, 각 대기실은 5x5 크기입니다.
2. 거리두기를 위하여 응시자들 끼리는 맨해튼 거리가 2 이하로 앉지 말아 주세요.
3. 단 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있을 경우에는 허용합니다.

2, 3번이 거리두기 규칙이다. 맨해튼 거리가 2 이하로 앉아야 하지만 파티션으로 막혀 있을 경우는 가능하다.

즉, P O P는 규칙을 어긴 것이고, P X P는 규칙을 준수한 것이다. 그럼 이 규칙을 어떻게 확인할까.

bfs를 통해 간단하게 확인할 수 있다. 나는 먼저 한 시험장에 있는 사람들을 people에 담고 각각의 사람이 거리두기를 지키고 있는지 검사했다.

 

한 사람을 검사할 때 해당 위치로 부터 맨해튼 거리 2 이하인 곳을 확인한다. 처음 위치에서 상하좌우로 한번씩 검사하고, 파티션이 있을 경우를 제외하고 빈 자리이면 큐에 넣어준다. 당연히 응시자가 있을 경우 즉시 False를 리턴한다.

그렇게 처음 상하좌우를 돌면 큐에 검사를 더 진행할 방향의 좌표들이 담겨있을 것이다. 여기서 이제 각 좌표마다 한번만 더 확인해주면 된다. 즉 두 번을 검사하면 되므로 count라는 변수를 생성해 관리한다.

count가 2가 되거나 큐에 좌표들이 담기지 않았으면 해당 사람 주위의 맨해튼 거리 2 이하로는 다 거리두기를 지키고 있다는 말이므로 True를 리턴한다.

 

while q:
  for _ in range(len(q)):
      y, x = q.popleft()
      visited[y][x] = True
      for i in range(4):
          nx = x + dx[i]
          ny = y + dy[i]
          if nx < 0 or ny < 0 or nx >= 5 or ny >= 5 or visited[ny][nx]:
              continue
          if place[ny][nx] == 'P':
              return False
          elif place[ny][nx] == 'X':
              continue
          else:
              q.append((ny, nx))
                    
  count += 1
  if count == 2 or not q:
      return True