2021 KAKAO 채용연계형 인턴십 거리두기 확인하기

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

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

 

생각보다 간단한 완탐 문제였다.
나는 place[r][c] 에 대해 DFS 를 하여 맨해튼 거리가 2 이하인 지점들을 모두 탐색하여 확인했다.

 

code는 다음과 같다.

dr = [0,0,1,-1]
dc = [1,-1,0,0]

def search(place, r, c, depth, v):
    
    if depth >= 3: return True
    elif r >= 5 or c >= 5 or r < 0 or c < 0: return True
    elif v[r*5+c] : return True
    elif place[r][c] == 'P' and depth != 0: 
        return False
    elif place[r][c] == 'X': return True

    v[r*5+c] = True
    
    for i in range(4):
        if not search(place, r+dr[i], c+dc[i], depth+1,v):
            return False
        
    return True

def get_answer(place):
    
    for r in range(5):
        for c in range(5):
            if place[r][c] == 'P':
                v = [False]*25
                if not search(place, r, c, 0,v):
                    print(r,c)
                    return 0 
    return 1
                
    
def solution(places):
    answer = []
    for place in places:
        answer.append(get_answer(place))
    
    return answer

문제의 input이 항상 5X5 이기 때문에, 최적화를 잘한다면 DFS없이 풀 수 있을 것이다.