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

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

프로그래머스

 

 

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

문제 설명

개발자를 희망하는 죠르디가 카카오에 면접을 보러 왔습니다.코로나 바이러스 감염 예방을 위해 응시자들은 거리를 둬서 대기를 해야하는데 개발 직군 면접인 만큼아래와 같은 규칙으로 대기실에 거리를 두고 앉도록 안내하고 있습니다.
대기실은 5개이며, 각 대기실은 5x5 크기입니다.거리두기를 위하여 응시자들 끼리는 맨해튼 거리1가 2 이하로 앉지 말아 주세요.단 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있을 경우에는 허용합니다.
예를 들어,

5개의 대기실을 본 죠르디는 각 대기실에서 응시자들이 거리두기를 잘 기키고 있는지 알고 싶어졌습니다. 자리에 앉아있는 응시자들의 정보와 대기실 구조를 대기실별로 담은 2차원 문자열 배열 places가 매개변수로 주어집니다. 각 대기실별로 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

제한사항

places의 행 길이(대기실 개수) = 5places의 각 행은 하나의 대기실 구조를 나타냅니다.places의 열 길이(대기실 세로 길이) = 5places의 원소는 P,O,X로 이루어진 문자열입니다.places 원소의 길이(대기실 가로 길이) = 5P는 응시자가 앉아있는 자리를 의미합니다.O는 빈 테이블을 의미합니다.X는 파티션을 의미합니다.입력으로 주어지는 5개 대기실의 크기는 모두 5x5 입니다.return 값 형식1차원 정수 배열에 5개의 원소를 담아서 return 합니다.places에 담겨 있는 5개 대기실의 순서대로, 거리두기 준수 여부를 차례대로 배열에 담습니다.각 대기실 별로 모든 응시자가 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 담습니다.

 

 

 

나의 풀이

# 거리두기 확인 함수를 사용하여 각 대기실별로 거리두기 여부를 판단
def solution(places):
    answer = []
    directions = [[-1, 0], [1,0], [0,1], [0,-1]]
     # 방문 여부를 나타내는 5x5 크기의 2차원 배열을 초기화
    visited = [[0]*5]*5
    
    # ["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"]
    for i in range(len(places)):
        result = []    
        visited = [[0 for col in range(5)] for row in range(5)]
        for j in range(len(places[i])):
            for k in range(len(places[i][j])):
       	 		# 응시자가 앉아있는 자리라면
                if places[i][j][k]  == "P":
                    #print(visited)
                    visited[j][k] = 1
                    # print("j : "+str(j)+" k : "+str(k))
                    # 거리두기 확인 함수를 호출하여 결과를 리스트에 추가
                    result.append(dfs(places[i], [j,k], directions, visited, 0))
                    
                    #print(result)
                    visited[j][k] = 0
        # 결과 리스트에 0이 포함되어 있으면 0을, 그렇지 않으면 1을 추가
        if 0 in result:
            answer.append(0)
        else:
            answer.append(1)
                        
                    
    return answer

def dfs(places, currentPosition, directions, visited, count): 
    if(count == 2): return 1
    result=1
    # print(visited)
    for direction in directions:
        newY=currentPosition[0]+direction[0] 
        newX=currentPosition[1]+direction[1]
         # 새로운 좌표(newY, newX)가 대기실 범위 내에 있는지 확인
        if (newX >=0 and newX <5) and (newY >=0 and newY <5) :
             # 만약 새로운 좌표에 응시자가 있다면 거리두기를 어기므로 0을 반환
            if visited[newY][newX] == 0:
                # print(places[newX][newY])
                if places[newY][newX] == "P":
                    # print("in")
                    return 0
                elif places[newY][newX] == "O":
                    visited[newY][newX] = 1
                    result= dfs(places, [newY, newX], directions, visited, count+1)
                    visited[newY][newX] = 0
                    # 결과가 0이면 바로 0을 반환하고, 그렇지 않으면 계속 진행
                    if result==0:
                        return 0
                    
    return result

 

 

설명

* 확인사항

문제에서는 5개의 대기실에 대한 정보가 문자열 배열 places로 주어짐
대기실은 5x5 크기이며, 각 좌석에는 응시자가 앉아있을 수 있음
응시자 간의 거리두기를 확인해야 하며, 응시자 사이의 거리가 2 이하이면 안됨
단, 파티션으로 막힌 경우에는 거리두기를 어기지 않음

 

* dfs사용이유

응시자와 응시자 간의 거리를 확인 / 각 대기실에서 응시자의 위치를 찾아야함 / 응시자 주변의 좌석을 탐색하면서 거리두기를 확인해야함

깊이 우선 탐색은 주변 좌석을 탐색하면서 더 깊게 들어갈 수 있으므로 응시자 주변의 좌석을 확인하기에 적합. DFS를 통해 주변 좌석을 순서대로 확인하면서 거리두기를 검사

*dfs로직

DFS를 사용하여 응시자 주변 좌석을 확인하고 거리두기를 검사
현재 위치에서 상, 하, 좌, 우로 이동하면서 응시자와 파티션  확인 => 거리두기를 어기면 0을 반환하고, 그렇지 않으면 1을 반환

 

*solution함수
places에 주어진 5개 대기실 각각에 대해 거리두기를 확인, 각 대기실에 대해 응시자의 좌석을 찾아 dfs 함수를 호출하여 거리두기를 검사하여 대기실별 결과를 리스트에 추가
결과 리스트에 0이 포함되어 있으면 해당 대기실은 거리두기를 어기는 경우가 있으므로 0을, 그렇지 않으면 1을 추가