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

문제 보기 : https://school.programmers.co.kr/learn/courses/30/lessons/81302

프로그래머스

 

 

풀이방식

먼저 가장  먼저 생각한 것은 BFS/ DFS 로 접근이다. 기본적으로는 상하좌우로 깊이 2가 되는 위치까지 파악하고 그 안에 P가 있다면 해당 PLACE는 0으로 RETURN 하는 베이직한 문제다! 그런데 여기에는 파티션 X를 추가해 문제를 조금 꼬았을 뿐이다. 파티션이 있으면 옆 칸이랑 이어지지 않는다. 따라서 파티션 X를 만나면 해당 위치에서는 다음 깊이로 넘어가지 않도록 코드를 작성했다.

 

코드작성

필자는 DFS로 재귀를 이용해서 풀었고 PLACE안에서 하나라도 FALSE가 나오면 뒤에는 살펴볼 필요가 없다. 따라서 시간 단축을 위해 sub_solution을 따로 작성해 return 하도록 만들었다. 또한 깊이 2면 처음 위치로 돌아 갈 수 있기 때문에(위로 한칸 갔다가 아래로 한칸 가는 경우 등) check함수를 돌리기 전에 그 위치는 "O"으로 바꿔주었다ㅎ 정석대로면 원래 위치를 따로 저장하거나 DFS재귀가 아닌 DFS와 queue를 이용한 풀이가 더 적절해 보인다!

 

def check(r, c, place, cnt):
    routes = ((0,1), (0,-1), (1,0), (-1,0))
    next_locs = []
    for route in routes:
        next_r = route[0] + r
        next_c = route[1] + c
        if 0 <= next_r < 5 and 0 <= next_c < 5:
            if place[next_r][next_c] == "P":
                return False
            elif place[next_r][next_c] == "O":
                next_locs.append((next_r, next_c))
    
    if cnt == 0:
        for loc in next_locs:
            if check(loc[0], loc[1], place, 1) == False:
                return False
    
    return True

def sub_solution(place):
    for r, row in enumerate(place):
        for i, el in enumerate(row):
            if el == "P":
                place[r] = place[r].replace('P', 'O', 1)
                if check(r, i, place, 0) == False:
                    return 0 
            
    return 1

def solution(places):
    return [sub_solution(place) for place in places]

 

 

후기

다른 분들 풀이도 살펴 봤는데 깊이가 2이다 보니 애초에 확인해야 할 위치 개수가 적기도 해 그냥 if로 때려박은 경우도 있었고 위에서 말씀한 바와 같이 dfs/queue를 이용한 풀이도 보였다. 이런 문제와 같이 경우의 수가 작은 문제는 if를 이용한 풀이가 시간적으로도 메모리상으로도 이득으로 보이긴 한다. 단, 필자는 알고리즘 공부가 목표라...ㅎ