[Programmers] 거리두기 확인하기 도움말

거리두기 확인하기

거리두기 확인하기 를 클릭하면 바로 이동한다.

응시자 별로 다른 응시자와의 거리를 구하면 된다.

그 중 하나라도 거리두기를 하고있지 않는다면 거리두기에 실패했다고 한다.

예전에 풀었던 문제인데 그때 풀었던 코드와 지금 코드를 비교해보니 풀이방법이 확연이 차이가 나서 신기했다.

---

from collections import deque


def BFS(place, start):
    visit = [[False for _ in range(5)] for _ in range(5)]
    visit[start[0]][start[1]] = True
    dirs = [[-1, 0], [0, 1], [1, 0], [0, -1]]

    start_info = start
    start_info.append(0)
    start_info.append('O')
    queue = deque([start_info])

    while queue:
        # 5. 현재 위치, 거리, 위치 정보를 가져온다.
        now_i, now_j, dist, point = queue.popleft()
        # 6. 현재 위치가 응시자이며 거리가 2 이하라면 거리두기를 하지 않은 것이다.
        if point == 'P' and dist <= 2:
            return False

        for value in dirs:
            visit_i, visit_j = now_i + value[0], now_j + value[1]
            if 0 <= visit_i < 5 and 0 <= visit_j < 5 and not visit[visit_i][visit_j]:
                if place[visit_i][visit_j] != 'X':
                    queue.append([visit_i, visit_j, dist + 1, place[visit_i][visit_j]])
                visit[visit_i][visit_j] = True

    return True


def chk_distance(place):
    people_loc = []
    # 1. 응시자들의 위치를 저장한다.
    for i in range(5):
        for j in range(5):
            if place[i][j] == 'P':
                people_loc.append([i, j])

    for loc in people_loc:
        # 2. 응시자 별로 다른 응시자끼리와의 거리를 구한다.
        # 3. 거리두기를 하지 않고 있는 경우 탐색을 종료하고 0을 반환한다.
        if not BFS(place, loc):
            return 0

    # 4. 거리두기를 하고 있는 경우 1을 반환한다.
    return 1


def solution(places):
    answer = []
    for place in places:
        answer.append(chk_distance(place))

    return answer


if __name__ == "__main__":
    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"]]

    print(solution(places))

---

from collections import deque


def is_corona(place, start, end):
    visit = [[False for _ in range(5)] for _ in range(5)]
    visit[start[0]][start[1]] = True
    tmp = [start[0], start[1], 0]
    queue = deque([tmp])
    dirs = [[-1, 0], [0, 1], [1, 0], [0, -1]]

    while queue:
        now_i, now_j, dist = queue.popleft()
        if [now_i, now_j] == end and dist <= 2:
            return True

        for val in dirs:
            visit_i, visit_j = now_i + val[0], now_j + val[1]
            if 0 <= visit_i < 5 and 0 <= visit_j < 5 and not visit[visit_i][visit_j]:
                if place[visit_i][visit_j] != 'X':
                    queue.append([visit_i, visit_j, dist + 1])
                visit[visit_i][visit_j] = True

    return False


def cal_distance(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])


def check_distance(place):
    people_idx = []
    for i in range(5):
        for j in range(5):
            if place[i][j] == 'P':
                people_idx.append([i, j])
    if not people_idx:
        return 1

    for i in range(len(people_idx)):
        for j in range(i + 1, len(people_idx)):
            distance = cal_distance(people_idx[i], people_idx[j])
            # 거리가 2 이하면서 거리두기가 안되고 있으면 0 반환
            if distance <= 2 and is_corona(place, people_idx[i], people_idx[j]):
                return 0
    return 1


def solution(places):
    answer = []
    for place in places:
        answer.append(check_distance(place))

    return answer


if __name__ == "__main__":
    places = [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"],
              ["PXOPX", "OXOXP", "OXPXX", "OXXXP", "POOXX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"],
              ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]]

    print(solution(places))