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

사용 언어: Python3

문제

거리두기 확인하기

풀이

다른 풀이

참고

from collections import deque

def solution(places):
    
    dx, dy = [0,-1,0,1],[1,0,-1,0]
    def BFS(place):
        start = []
        # start 지점 초기화
        for i in range(5):
            for j in range(5):
                if place[i][j] == 'P':
                    start.append((i, j))
        
        for s in start: # ✅ 시작 지점이 여러 개이기 때문에 for문
            q = deque()
            visited = [[0] * 5 for _ in range(5)] # 방문했는지 체크
            dist = [[0] * 5 for _ in range(5)] # ✅ 각각의 출발점 s로부터의 거리
            
            q.append(s)
            visited[s[0]][s[1]] = 1
            
            while q:
                x, y = q.popleft()
                for w in range(4):
                    xx, yy = x+dx[w], y+dy[w]
                    if xx<0 or xx>=5 or yy<0 or yy>=5:
                        continue
                    if place[xx][yy] == 'X' or visited[xx][yy]:
                        continue
                    dist[xx][yy] = dist[x][y] + 1 # ✅ 거리 업데이트
                    if place[xx][yy] == 'O': # 빈 테이블('O')은 열려있는 공간이기 때문에 탐색이 가능하다
                        q.append((xx, yy))
                        visited[xx][yy] = 1
                    else: # ✅ 또 다른 P를 만나면 경로 거리를 판단해서 맨해튼 거리 2보다 작으면 거리두기 실패 (return 0)
                        if dist[xx][yy] <= 2:
                            return 0 # 거리두기 지키지 않은 것
        return 1 # 모든 응시자가 거리두기를 지키고 있음
                    
    ans = []
    for place in places:
        ans.append(BFS(place))
                
    return ans

• 테스트 케이스: 통과
• 제출 결과: 통과
• 겉으로 봤을 때는, 응시자가 앉아있는 자리(P)에서 맨해튼 거리가 2인 다른 P가 있는 지 체크하는 문제지만,
  바꿔서 생각하면 시작점을 P로 하고 벽(X)이 아닌 지점을 방문하는 BFS 문제로 풀 수 있다.

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기