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

 

📌문제

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

 

🎖️난이도

Level 2

 

✔️풀이

from collections import deque

def bfs(graph):
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    
    for i in range(5):
        for j in range(5):
            if graph[i][j] == 'P':
                queue = deque()
                queue.append((i, j, 0))
                visited = set()
                visited.add((i, j))
                
                while queue:
                    x, y, d = queue.popleft()
                    for k in range(4):
                        nx = x + dx[k]
                        ny = y + dy[k]
                        nd = d + 1
                        if nx in range(0, 5) and ny in range(0, 5) and (nx, ny) not in visited:
                            visited.add((nx, ny))
                            if graph[nx][ny] == 'P':
                                if nd <= 2: # 따라서 nd가 1이든 2든 둘 다 X!
                                    return 0
                            
                            # O가 바로 옆에 하나라도 있던애들이 큐에 있는 것
                            elif graph[nx][ny] == 'O' and nd == 1:
                                # 탐색 가능한(유망한) 방향이면 큐에 추가
                                queue.append((nx, ny, nd))
                                               
    return 1

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

 

🧠노트

BFS...

레벨 2인데도 어렵다... 카카오 기출이라 그런가..?

 

무튼 주석처리된 부분을 잘 이해하기!

 

거리가 1인 곳들 중에서 'O'인 곳을 queue에 넣었다는 것은,
추후 그 곳으로부터 거리가 2일 때는 뭐가 됐든 'P'가 나오면 안된다는 뜻 !

(거리 2가 대각선이든, 일렬로 두칸 옆이든 상관 X)

 

추가적으로,

queue에 넣을 때 거리(d)도 같이 넣어서(nx, ny, nd) 탐색 시작 지점으로부터의 거리를 계속 체크할 수 있다는 점도 배웠다.

 

복습할 것!

 

🔍참고

-