[Python] 프로그래머스 거리두기 확인하기 & 프로그래머스 전화번호 목록

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

from collections import deque

d_row = [0, -1, 0, 1]
d_col = [1, 0, -1, 0]


def solution(places):
    answer = []
    for i in range(5):
        result = bfs(places[i])
        answer.append(result)

    return answer


def bfs(place):
    queue = deque()
    visited = [[False] * 5 for _ in range(5)]
    for i in range(5):
        for j in range(5):
            if place[i][j] == 'P':
                queue.append([i, j, False])
            if place[i][j] == 'O':
                queue.append([i, j, False])

    while queue:
        x, y, flag = queue.popleft()
        for i in range(4):
            dx = d_row[i] + x
            dy = d_col[i] + y
            if 0 <= dx < 5 and 0 <= dy < 5:
                if place[x][y] == 'P' and place[dx][dy] == 'P':
                    return 0
                elif flag == False and not visited[dx][dy] and place[x][y] == 'O' and place[dx][dy] == 'P':
                    flag = True
                    queue.append([dx, dy, True])
                elif place[x][y] == 'O' and place[dx][dy] == 'P' and flag:
                    return 0

    return 1

places = [["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"]]
solution(places)

 

풀이

테이블('O')기준으로 4면에 사람('P')가 있는지 체크한다.

만약 사람이 있으면 남은 3면에는 사람이 없어야 거리두기가 가능하기때문에 사람이 나오면 flag = True로 설정하고 queue에 넣어준후 반복문이 끝나기전까지 사람이 또 나오면 return 0을 해준다.

 

# 프로그래머스 전화번호 목록

def solution(phone_book):
    phone_book.sort()
    for i in range(len(phone_book)-1):
        if len(phone_book[i]) <= len(phone_book[i+1]):
            i_len = len(phone_book[i])
            if phone_book[i] == phone_book[i+1][:i_len]:
                return False
    return True