거리두기 확인하기 (81302번) - 프로그래머스 (Programmers)

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

프로그래머스

 

 

프로그래머스 - 거리두기 확인하기 (81302번)

 

난이도 : Lv 2

알고리즘&자료구조 : BFS (너비우선탐색)

 

 

dr = [1, -1, 0, 0]
dc = [0, 0, 1, -1]


def bfs(place):
    for r in range(5):
        for c in range(5):
            if place[r][c] == "P":
                v = [[False]*5 for _ in range(5)]
                v[r][c] = True
                q = [(r, c)]
                for _ in range(2):
                    tmp = []
                    for r, c in q:
                        for i in range(4):
                            rr, cc = r+dr[i], c+dc[i]
                            if 0 <= rr < 5 and 0 <= cc < 5:
                                if place[rr][cc] == 'X' or v[rr][cc]:
                                    continue
                                if place[rr][cc] == 'P':
                                    return 0
                                tmp.append((rr, cc))
                                v[rr][cc] = True
                    q = tmp    
    return 1


def solution(places):
    return [bfs(place) for place in places]

 

 

2021 카카오 채용연계형 인턴십 기출문제이다.

전형적인 BFS 문제이다.

 

 

---

 

 

① places의 각 place에 대해서, BFS 를 수행한다.

 

▷ (0, 0) 부터 (4, 4) 까지 하나씩 순회하면서,

'P' 가 발견되면, 그 위치를 시작으로 BFS 를 실행한다.

 

▷ 거리두기 위반은 'P'와 'P' 간 거리가 2 이하일 때만 해당되므로,

while 문이 아닌 for 문을 활용해서, for _ in range(2) 로 딱 두 번 이하로만 실행되게 한다.

 

▷ 그 두 번의 실행 중에, 만약 다른 'P'에 접근하게 된다면

해당 place는 거리두기 규칙을 위반하고 있으므로,

0 을 반환한다.