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

특수한 조건을 확인해보자

1. 각 대기실의 크기는 5x5이다.
2. 대기실의 원소는 P, O, X뿐이다.

대기실의 크기가 고정되어있으므로 좌표와 관련된 함수를 간단하게 작성할 수 있다

def show_place(places):
'''각 place를 출력해보는 함수'''
    for i in range(5):
        for j in range(5):
            print(places[i][j], end='')
        print()
    print()
    
def get_persons(place):
'''각 대기실에서 사람 위치정보를 저장하는 배열을 반환'''
    persons = []
    for i in range(5):
        for j in range(5):
            if place[i][j] == 'P':
                persons.append([i, j])
    return persons


def get_visit():
''' BFS할때 방문 체크 배열을 초기화하여 반환'''
    return [[False]*5 for _ in range(5)]
    
    
def is_valid(x, y, place):
''' 각 좌표가 사람이 존재할 수 있는지 좌표 적합성을 반환'''
    check1 = (x >= 0) and (x < 5) and (y >= 0) and (y < 5)
    check2 = check1 and (place[x][y] != 'X')
    return check2    
    

이제 사람이 있는 위치에서 BFS를 이용하여 거리가 2 이내에 사람이 있는지 확인하는 코드를 작성한다. (사실 거리가 2 이므로 if를 도배해서 확인할 수도 있다)
BFS에서 각 위치에서 다음 위치가 사람이고 거리가 2 이하면 거리두기 위반이다

def check_rule_break(person, place, visit):
    x, y = person
    visit[x][y] = True # 방문표시
    
    is_break_rule = False # 거리두기 위반 여부
    
  
    queue = deque() # BFS에 활용할 큐
    queue.append([x, y, 0])
    # 큐의 원소는 리스트이며,
    # 각 리스트의 원소는 x좌표, y좌표, 처음person과의 거리이다
    
    # 큐가 비어있지 않고, 거리두기 위반하지 않으면 계속 BFS 탐색
    while queue and not is_break_rule:
        pos = queue.popleft()
        x, y, d = pos
        #print(pos)
        
        # 거리가 2 초과인 곳부터는 더이상 탐색하지 않아도 된다
        if d > 2:
            break

	# 4가지 방향 탐색
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            # 새로운 좌표 적합성 판단
            if is_valid(nx, ny, place) and not visit[nx][ny]:
                queue.append([nx, ny, d + 1])
                # 새로운 좌표가 사람이고 거리두기 위반할 경우
                if place[nx][ny] == 'P' and d + 1 <= 2:
                    is_break_rule = True
                    #print(nx, ny)
                    break

    #print(is_break_rule)
    return 1 if is_break_rule else 0

완성된 코드는 다음과 같다

from collections import deque

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

def show_place(places):
    for i in range(5):
        for j in range(5):
            print(places[i][j], end='')
        print()
    print()
    
def get_persons(place):
    persons = []
    for i in range(5):
        for j in range(5):
            if place[i][j] == 'P':
                persons.append([i, j])
    return persons


def get_visit():
    return [[False]*5 for _ in range(5)]

def is_valid(x, y, place):
    check1 = (x >= 0) and (x < 5) and (y >= 0) and (y < 5)
    check2 = check1 and (place[x][y] != 'X')
    return check2

def check_rule_break(person, place, visit):
    x, y = person
    visit[x][y] = True
    
    is_break_rule = False
    
    queue = deque()
    queue.append([x, y, 0])
    
    while queue and not is_break_rule:
        pos = queue.popleft()
        x, y, d = pos
        #print(pos)
        if d > 2:
            break

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if is_valid(nx, ny, place) and not visit[nx][ny]:
                queue.append([nx, ny, d + 1])
                if place[nx][ny] == 'P' and d + 1 <= 2:
                    is_break_rule = True
                    #print(nx, ny)
                    break

    #print(is_break_rule)
    return 1 if is_break_rule else 0
        
        
    
def solution(places):
    answer = []
    for place in places:
        #show_place(place)
        persons = get_persons(place)
        break_counter = 0
        for person in persons:
            visit = get_visit()
            break_counter += check_rule_break(person, place, visit)
            #print('=====>', person, break_counter)
        if break_counter == 0:
            answer.append(1)
        else:
            answer.append(0)
        #print()
    return answer