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

Loopy·2021년 7월 21일
6

프로그래머스

목록 보기
23/32
post-thumbnail

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


🧐 문제 설명


😍 나의 풀이

거리두기를 확인하는 방법을 BFS로 어떻게 해결할 것인가?

이 문제는 겉으로 봤을 때는, 응시자가 앉아있는 자리(P)에서 맨해튼 거리가 2인 다른 P가 있는 지 체크하는 문제지만, 바꿔서 생각하면 시작점을 P로 하고 벽('X')이 아닌 지점을 방문하는 BFS 문제로 풀 수 있다. 크기가 5x5인 매트릭스로 고정이기 때문에 모두 탐색하는 방법도 시간이 얼마 안 걸리긴 할 것..

1. BFS에서 출발 지점은?

BFS를 사용하려면 경로 탐색을 시작할 출발점이 필요하다. 이 문제에서는 응시자가 앉아있는 자리(P)가 출발 지점이 된다. P는 없을 수도 있고, 여러개일 수도 있기 때문에 시작점이 되는 P의 좌표 인덱스를 모두 구해서 start 리스트에 저장한다.

한 응시자라도 거리두기 규칙을 위반했을 때 거리두기는 실패한 것이므로(return 0) 시작점들이 저장되어있는 start 리스트를 반복하며 check한다.

→ 이 때, start 리스트에 있는 P를 하나씩 BFS 하면서 거리두기 여부 check가 완료되고 나면 '방문 처리' 리스트인 visited, '경로 길이' 리스트인 distance를 모두 초기화해야 한다.

2. 빈 테이블('O'), 파티션('X')에 대한 처리는?

P는 BFS 탐색을 시작할 때 다른 P를 만나거나 모든 탐색 가능한 지점을 방문할 때까지 상하좌우 이동을 반복한다. 그렇다면 이동 가능한 위치는 어디일까?

  • 탐색 중 파티션('X')를 만날 때
    P가 파티션('X')을 만나면 이는 벽에 가로막힌 것으로 해당 방향으로는 탐색이 불가능하다.

  • 탐색 중 빈 테이블('O')을 만날 때
    빈 테이블('O')은 마찬가지로 열려있는 공간이기 때문에 P가 탐색이 가능하다.

  • 탐색 중 또 다른 'P' 을 만날 때
    P가 이동을 계속 하다가 또 다른 P를 만나면 경로 거리를 판단해서 맨해튼 거리 2보다 작으면 거리두기 실패(return 0)을 판단하고 2보다 크면 거리두기 해당 P는 거리두기 성공을 의미한다. (P가 여러 개일 수 있으니 모든 P의 시작점에서 BFS 탐색에 성공해야 return 1을 반환해야함에 주의!)

결과적으로 P의 다음 진행할 위치가 'O'이고 그 지점이 이미 방문하지 않은 곳일 때만 BFS를 진행하면 된다.

from collections import deque

def bfs(p):
    start = []
    
    for i in range(5): # 시작점이 되는 P 좌표 구하기
        for j in range(5):
            if p[i][j] == 'P':
                start.append([i, j])
    
    for s in start:
        queue = deque([s])  # 큐에 초기값
        visited = [[0]*5 for i in range(5)]   # 방문 처리 리스트
        distance = [[0]*5 for i in range(5)]  # 경로 길이 리스트
        visited[s[0]][s[1]] = 1
        
        while queue:
            y, x = queue.popleft()
        
            dx = [-1, 1, 0, 0]  # 좌우
            dy = [0, 0, -1, 1]  # 상하

            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]

                if 0<=nx<5 and 0<=ny<5 and visited[ny][nx] == 0:
                    
                    if p[ny][nx] == 'O':
                        queue.append([ny, nx])
                        visited[ny][nx] = 1
                        distance[ny][nx] = distance[y][x] + 1
                    
                    if p[ny][nx] == 'P' and distance[y][x] <= 1:
                        return 0
    return 1


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

👏 다른 사람의 풀이

출처 : Dongmin Lee님의 기록하자 벨로그
직접 이중 반복문으로 한 칸씩 다 check하는 방법을 쓰신 풀이.

def solution(places):
    answer = [];
    
    #place를 하나씩 확인
    for p in places:
        
        #거리두기가 지켜지지 않음을 확인하면 바로 반복을 멈추기 위한 key
        key = False;
        nowArr = [];
        
        #이번 place를 nowArr에 담아줍니다.
        for n in p:
            nowArr.append(list(n));
        
        #이중 for문을 이용해 하나씩 확인합니다.
        for i in range(5):
            if key:
                break;
                
            for j in range(5):
                if key:
                    break;
                
                #사람을 찾아내면 판단을 시작합니다.
                if nowArr[i][j] == "P":
                    
                    if i+1<5:
                    	#만약 바로 아랫부분에 사람이 존재하면 break
                        if nowArr[i+1][j] == "P":
                            key = True;
                            break;
                        #만약 아랫부분이 빈테이블이고 그 다음에 바로 사람이 있다면 한칸 떨어져 있더라도 맨허튼 거리는 2이므로 break
                        if nowArr[i+1][j] == "O":
                            if i+2<5:
                                if nowArr[i+2][j] == "P":
                                    key = True;
                                    break;
                    #바로 오른쪽 부분에 사람이 존재하면 break    
                    if j+1<5:
                        if nowArr[i][j+1] == "P":
                            key = True;
                            break;
                         #만약 오른쪽 부분이 빈테이블이고 그 다음에 바로 사람이 있다면 한칸 떨어져 있더라도 맨허튼 거리는 2이므로 break   
                        if nowArr[i][j+1] == "O":
                            if j+2<5:
                                if nowArr[i][j+2] == "P":
                                    key = True;
                                    break;
                    #우측 아래 부분입니다.
                    if i+1<5 and j+1<5:
                    	#만약 우측 아래가 사람이고, 오른 쪽 또는 아랫부분중 하나라도 빈테이블이면 break
                        if nowArr[i+1][j+1] == "P" and (nowArr[i+1][j] == "O" or nowArr[i][j+1] == "O"):
                            key = True;
                            break;
                    
                    #좌측 아래부분입니다.
                    if i+1<5 and j-1>=0:
                    	#만약 좌측 아래가 사람이고, 왼쪽 또는 아랫부분중 하나라도 빈테이블이면 break
                        if nowArr[i+1][j-1] == "P" and (nowArr[i+1][j] == "O" or nowArr[i][j-1] == "O"):
                            key = True;
                            break;
        
        #위의 for문동안 key가 True로 변경되었다면 거리두가기 지켜지지 않은것 이므로 0을 answer에 추가
        if key:
            answer.append(0);
        else:
        #key가 false로 끝났다면 거리두기가 지켜졌으므로 1 추가
            answer.append(1);

    #끝!
    return answer;
profile
공부 쫌 해!!!😂

0개의 댓글