🎁문제 링크

거리두기 확인

🎁문제 풀이

접근 순서

1. BFS 탐색을 통해 거리가 2이하 안에 P를 발견하면 거리두기를 지키지 않는것이다.
2. Places 안의 각각의 palce에서 거리두기를 지키는지 확인 하고 그 결과를 0 or 1로 저장한다.

1. BFS 탐색을 통해 거리가 2이하 안에 P를 발견하면 거리두기를 지키지 않는것이다.

from collections import deque

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

def bfs(x, y, place):
    visited = [[0] *5 for _ in range(5)]
    queue = deque()
    queue.append((x,y,0))
    visited[x][y] = 1

    while queue:
        x, y, dist = queue.popleft()
        # 거리두기를 지키지 않기 때문에 바로 return 해준다.
        if 0 < dist < 3 and place[x][y] == 'P':
            return False
        if dist > 2:
            break
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            nd = dist + 1
            # board 안에 들어와 있고, 벽이 아니고, 방문한적이 없다면 진행한다.
            if 0 <= nx < 5 and 0 <= ny < 5 and place[nx][ny] != 'X' and not visited[nx][ny]:
                queue.append((nx,ny, nd))
                visited[nx][ny] = 1
    return True

2. Places 안의 각각의 palce에서 거리두기를 지키는지 확인 하고 그 결과를 0 or 1로 저장한다.

def check(place):
    for i in range(len(place)):
        for j in range(len(place)):
            if place[i][j] == 'P':
                if not bfs(i, j, place):
                    return False
    return True 

def solution(places):
    answer = []
    for place in places:
        if check(place):
            answer.append(1)
        else:
            answer.append(0)
    return answer

Check 함수를 이용하여 각각의 place일때 거리두기를 하고 있는지 확인한다. 그 뒤에 Solution 함수에서 Check에서 return 해준 참/거짓 값을 이용하여 answer 리스트에 값을 저장한다.

🎁전체 풀이 코드

from collections import deque

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

def bfs(x, y, place):
    visited = [[0] *5 for _ in range(5)]
    queue = deque()
    queue.append((x,y,0))
    visited[x][y] = 1

    while queue:
        x, y, dist = queue.popleft()
        # 거리두기를 지키지 않기 때문에 바로 return 해준다.
        if 0 < dist < 3 and place[x][y] == 'P':
            return False
        if dist > 2:
            break
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            nd = dist + 1
            # board 안에 들어와 있고, 벽이 아니고, 방문한적이 없다면 진행한다.
            if 0 <= nx < 5 and 0 <= ny < 5 and place[nx][ny] != 'X' and not visited[nx][ny]:
                queue.append((nx,ny, nd))
                visited[nx][ny] = 1
    return True

def check(place):
    for i in range(len(place)):
        for j in range(len(place)):
            if place[i][j] == 'P':
                if not bfs(i, j, place):
                    return False
    return True 

def solution(places):
    answer = []
    for place in places:
        if check(place):
            answer.append(1)
        else:
            answer.append(0)
    return answer

🥇주의 사항

더 이상 탐색해도 되지 않을 때는 조건을 이용하여 쓸대없는 탐색을 하지 않도록 break를 이용하여 탐색을 종료시켜줘야 한다.
이 문제 같은 경우 BFS 탐색을 통해 반환되는 값이 True/ False 값이고 여러개의 리스트들을 확인해줘야 한다. 따라서 check 라는 함수를 이용하여 한번에 처리해주는것이 코드를 작성하는데 있어서 훨씬 용이하다.