[Level 2] 거리두기 확인하기

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

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

---

접근

대기실 내에서 사람의 좌표를 기준으로 BFS를 진행하고 맨해튼 거리가 2이하인 지원자가 있으면 False를 반환하도록 하였다. 

 

구현

- 먼저 문자열로 되어있는 대기실의 정보를 2차원 리스트의 형태로 변환하여 board에 저장한다.

- 이제 2차원 리스트를 탐색하여 P일 때 BFS를 진행한다.

- BFS에서 반환된 값이 False일 때 0을 추가하고 종료한다.

- 그렇지 않으면 1을 추가한다. 여기서 for문에 대한 else를 하였는데 대기실 내에 지원자가 없을 수도 있기 때문이다.

- 이렇게 하지않고 탐색 전에 flag를 선언하여 True로 초기화 한다음에 할 수도 있을 것이다.

def solution(places):
    answer = []
    N = 5
    for place in places:
        board = []
        for i in range(N):
            board.append(list(place[i]))

        pos = [(y, x) for y in range(N) for x in range(N)]
        for y, x in pos:
            if board[y][x] == 'P':
                flag = bfs(board, y, x)
                if not flag:
                    answer.append(0)
                    break
        else:
            answer.append(1)

    return answer

- BFS를 진행한다.

- 만약 현재 위치가 P이고 맨해튼 거리가 3이하이면서 1은 아니라면 False를 반환한다.

- 다음 위치를 탐색할 때는 범위를 벗어나지 않고 X가 아니도록 한다.

- X가 아닌 곳만 탐색할 수 있도록 하여 가림막으로 되어 있는 곳은 거리두기를 잘 지켰다고 판단할 수 있도록 한다.

def bfs(board, y, x):
    q = deque()
    dist = [[0 for _ in range(5)] for _ in range(5)]
    dy = [1, -1, 0, 0]
    dx = [0, 0, 1, -1]
    dist[y][x] = 1
    q.append([y, x])
    while q:
        cy, cx = q.popleft()
        if board[cy][cx] == 'P' and dist[cy][cx] <= 3 and dist[cy][cx] != 1:
            return False
        for d in range(4):
            ny = cy + dy[d]
            nx = cx + dx[d]
            if check_range(ny, nx, 5) and board[ny][nx] != 'X' and dist[ny][nx] == 0:
                q.append([ny, nx])
                dist[ny][nx] = dist[cy][cx] + 1
    return True

---

전체 코드

from collections import deque


def check_range(y, x, N):
    return (0 <= y < N) and (0 <= x < N)


def bfs(board, y, x):
    q = deque()
    dist = [[0 for _ in range(5)] for _ in range(5)]
    dy = [1, -1, 0, 0]
    dx = [0, 0, 1, -1]
    dist[y][x] = 1
    q.append([y, x])
    while q:
        cy, cx = q.popleft()
        if board[cy][cx] == 'P' and dist[cy][cx] <= 3 and dist[cy][cx] != 1:
            return False
        for d in range(4):
            ny = cy + dy[d]
            nx = cx + dx[d]
            if check_range(ny, nx, 5) and board[ny][nx] != 'X' and dist[ny][nx] == 0:
                q.append([ny, nx])
                dist[ny][nx] = dist[cy][cx] + 1
    return True


def solution(places):
    answer = []
    N = 5
    for place in places:
        board = []
        for i in range(N):
            board.append(list(place[i]))

        pos = [(y, x) for y in range(N) for x in range(N)]
        for y, x in pos:
            if board[y][x] == 'P':
                flag = bfs(board, y, x)
                if not flag:
                    answer.append(0)
                    break
        else:
            answer.append(1)

    return answer