프로그래머스 거리두기 확인하기(Python)

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

코딩테스트 연습 - 거리두기 확인하기

이번에도 레벨 2 문제를 골랐다. 문제를 보고 두 가지 생각이 들었다. 모든 경우를 if-elif-else로 푸는 방법과 DFS 또는 BFS를 이용해 푸는 방법이었다. BFS를 활용해서 풀기에는 뭔가 막막한 느낌이 들어서 무지성 if-elif-else 방식을 골랐다.

하나하나 풀어가다보니 나 스스로도 어디를 적고 있는지 헷갈리고, 모든 경우를 생각해야 하다 보니 시간이 너무 오래 지체되었다. 이건 아니다는 생각이 들어 바로 다른 사람의 풀이를 찾아봤다. 역시, 아래 사이트는 BFS 방식을 채택했다.

https://velog.io/@sem/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-LEVEL2-%EA%B1%B0%EB%A6%AC%EB%91%90%EA%B8%B0-%ED%99%95%EC%9D%B8%ED%95%98%EA%B8%B0-Python

[프로그래머스] LEVEL2 거리두기 확인하기 (Python)

완벽히 베끼지는 않고(그래 봤자 98% 똑같은데?) 사소하게 몇 군데를 바꿔서 풀어보았다.

(거의) 다른 사람의 풀이

BFS를 푸는데 queue를 빼놓을 수 없다. 파이썬의 collections 패키지에서 deque를 제공한다. deque의 자세한 사용법은 아래 사이트를 참고하자.

https://docs.python.org/ko/3.8/library/collections.html?highlight=deque#collections.deque 

collections — Container datatypes — Python 3.8.13 문서

다른 사람의 풀이의 순서를 나열하면 아래와 같다.

1. 모든 "P"의 좌표를 BFS의 시작 지점으로 선택한다.
2. 각 "P"의 좌표별로 deque를 생성하고, 방문 여부를 초기화한다.
3. 탐색 시작점을 기준으로 위, 아래, 왼쪽, 오른쪽 자리를 살핀다.
4. 하나의 경우라도 거리두기가 지켜지지 않으면 0을, 아니면 1을 반환한다.

내가 여기서 약간의 변화를 준 구간이 있다.

• BFS 탐색 범위: 다른 사람의 코드대로 가면 맨해튼 거리가 2를 넘어선 범위에 대해서도 탐색을 이어간다.
• 각 자리까지의 거리: 다른 사람의 코드대로면 탐색을 새로 할 때마다 5 * 5의 리스트를 초기화해야 한다.

이를 구현한 코드가 아래의 코드이다.

# 참고: https://velog.io/@sem/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-LEVEL2-%EA%B1%B0%EB%A6%AC%EB%91%90%EA%B8%B0-%ED%99%95%EC%9D%B8%ED%95%98%EA%B8%B0-Python
from collections import deque

def check(_place):
    start_points = []
    for i in range(len(_place)):
        for j in range(len(_place[i])):
            if _place[i][j] == "P":
                start_points.append((i, j))
            
    for s_point in start_points:
        bfs_q = deque([s_point])
        visited = [[False] * len(_place) for _ in range(len(_place))]    # 대기실이 정방형이라 이렇게 가능
        visited[s_point[0]][s_point[1]] = True
        
        while bfs_q:
            r, c = bfs_q.popleft()
            dr = [-1, 1, 0, 0]
            dc = [0, 0, -1, 1]
            
            for i in range(len(dr)):
                nr, nc = r + dr[i], c + dc[i]
                if 0 <= nr < len(_place) and 0 <= nc < len(_place) and not visited[nr][nc]:
                    if _place[nr][nc] == "O":
                        if abs(nr - s_point[0]) + abs(nc - s_point[1]) < 2:
                            bfs_q.append((nr, nc))
                            visited[nr][nc] = True
                    elif _place[nr][nc] == "P":
                        return 0
    return 1
            
def solution(places):
    answer = [check(place) for place in places]
    return answer

프로그래머스 채점 서버에서 채점한 결과, 최대 0.15ms, 10.5MB만큼 소모했다.

 

아예 생각을 못 한 풀이가 아니었어서 살짝 아쉬웠던 문제였다...