코딩테스트 문제 : 거리두기 확인하기 (프로그래머스)

문제

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

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

 

나의 코드

import collections
ways = [[0,-1],[1,0],[0,1],[-1,0]]

def solution(places):
    answer = []
    for place in places:
        check = 1                       #거리두기를 잘한다는 가정에서 시작한다.
        for x in range(5):              #places에서 대기실 하나를 불러온다.
            for y in range(5):          #대기실에서 P를 찾는다.
                if place[x][y] == "P":  #P를 찾았으면 bfs함수를 호출한다.
                    check = min(bfs(place.copy(),x,y),check)
                    #거리두기를 하지 않는 사람이 있었다면 계속 bfs유무와 상관없이 0이 선택된다. 
                    
        answer.append(check) #대기실 결과를 answer에 추가한다.
    return answer

def bfs(place, x, y):
    dq = collections.deque([[x,y,0]]) #처음 시작할 때 P의 위치를 가진 dequeue를 생성한다.
    init_p = list(place[x])           #자기 자신을 위치에서 맴돌지 않도록 처음 P를 X처리한다.
    init_p[y] = "X"                   #처음 위치 P를 X로 처리해도 상관없다.
    place[x] = "".join(init_p)
    while dq:                         #bfs 시작
        target = dq.popleft()         #dq에서 맨 앞 요소를 pop한다.
        
        if place[target[0]][target[1]] == "P" and target[2] != 0:#탐색중에 P를 만나면 바로 종료
            return 0                                             #target[2]==0이면 자기자신이란 뜻
        
        if target[2] < 2:             #세 번이상 이동 한 경우를 생각할 필요가 없다. 두번 이동한 것 까지에서 멈춘다.
            for way in ways:          #이동할 수 있는 방향 4가지를 모두 확인하여 이동가능하면 queue에 추가한다.
                if target[2] <= 1:    #아직 이동 횟수가 1번이라면 더 이동할 수 있다.
                    i = target[0] + way[0]
                    j = target[1] + way[1]
                    
                    if out_check(i,j):      #index범위를 넘어간 경우는 제외해야 한다.
                        if place[i][j] != "X": #가고자 하는 방향이 막혀있지 않다면 queue에 추가한다.
                            dq.append([i,j,target[2] + 1])
                            
                            if place[i][j] == "O": #이동하였으면 다른 탐색에서 이동한 방향으로 오지 못하도록 X처리한다.
                                tmp = list(place[i])
                                tmp[j] = "X"
                                place[i] = "".join(tmp)
    return 1

def out_check(x,y): #범위를 넘어갔는지 확인하는 함수
    if 0 <= x < 5 and 0 <= y < 5:
        return True
    else:
        return False

P에서 시작해서 2번 움직인 경로까지에 또 다른 P가 있다면 0 없다면 1을 표시하면 된다고 생각했다.

제한된 깊이에서 탐색을 하는데 BFS를 이용하였고 [행, 열, 깊이] 형식으로 Queue에 추가하며 처리하였다.

dq에서 각각의 요소 [x, y, d]는 x,y좌표까지 오는데 d번 움직여야 한다는 의미이다.

좌표를 dq에 넣을 때 지나왔다는 표시로 X로 바꾸는데 기존의 대기실에 영향을 주지 않기 위해 copy()를 인수로 주었다.

 

print로 상황을 볼 수 있는 코드: 아래 코드를 복사 후 실행하면 상황을 볼 수 있다.

import collections
ways = [[0,-1],[1,0],[0,1],[-1,0]]

def solution(places):
    answer = []
    for place in places:
        print("{}대기실 탐색시작".format(place))
        check = 1                       #거리두기를 잘한다는 가정에서 시작한다.
        for x in range(5):              #places에서 대기실 하나를 불러온다.
            for y in range(5):          #대기실에서 P를 찾는다.
                if place[x][y] == "P":  #P를 찾았으면 bfs함수를 호출한다.
                    print("{}, {}좌표를 확인합니다".format(x,y))
                    check = min(bfs(place.copy(),x,y),check)
                    #거리두기를 하지 않는 사람이 있었다면 계속 bfs유무와 상관없이 0이 선택된다. 
        print("----------------------------------------------------------------")
                    
        answer.append(check) #대기실 결과를 answer에 추가한다.
    return answer

def bfs(place, x, y):
    dq = collections.deque([[x,y,0]]) #처음 시작할 때 P의 위치를 가진 dequeue를 생성한다.
    init_p = list(place[x])           #자기 자신을 위치에서 맴돌지 않도록 처음 P를 X처리한다.
    init_p[y] = "X"                   #처음 위치 P를 X로 처리해도 상관없다.
    place[x] = "".join(init_p)
    while dq:                         #bfs 시작
        target = dq.popleft()         #dq에서 맨 앞 요소를 pop한다.
        print("{}, {}좌표 : {}이동했을 때의 상황에서 시작".format(target[0],target[1],target[2]))
        if place[target[0]][target[1]] == "P" and target[2] != 0:
            return 0
        
        print_tmp=[]
        
        if target[2] < 2:             #세 번이상 이동 한 경우를 생각할 필요가 없다. 두번 이동한 것 까지에서 멈춘다.
            for way in ways:          #이동할 수 있는 방향 4가지를 모두 확인하여 이동가능하면 queue에 추가한다.
                if target[2] <= 1:    #아직 이동 횟수가 1번이라면 더 이동할 수 있다.
                    i = target[0] + way[0]
                    j = target[1] + way[1]
                    
                    if out_check(i,j):      #index범위를 넘어간 경우는 제외해야 한다.
                        if place[i][j] != "X": #가고자 하는 방향이 막혀있지 않다면 queue에 추가한다.
                            dq.append([i,j,target[2] + 1])
                            print_tmp.append([i,j])
                            
                            if place[i][j] == "O": #이동하였으면 다른 탐색에서 이동한 방향으로 오지 못하도록 X처리한다.
                                tmp = list(place[i])
                                tmp[j] = "X"
                                place[i] = "".join(tmp)
            if len(print_tmp)!=0:
                print("탐색 결과 {}좌표들로 이동가능 함을 확인".format(print_tmp))
            print("탐색 후 dq상태: {}".format(dq))
            print("")
    return 1

def out_check(x,y): #범위를 넘어갔는지 확인하는 함수
    if 0 <= x < 5 and 0 <= y < 5:
        return True
    else:
        return False