프로그래머스 - 거리두기 확인하기 (2021 카카오 채용연계 인턴십) / Level 2

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

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

 

풀이

def solution(places):
    answer = []
    global dx
    global dy
    global room
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    n = 5
    
    for place in places:
        flag = False
        room = [list(i) for i in place]
        
        for i in range(n):
            for j in range(n):
                if room[i][j] == 'P':
                    if firstSearch(i, j) == 0:
                        flag = True
                        break
            if flag:
                break
        if flag:
            answer.append(0)
        else:
            answer.append(1)
        
    return answer

def firstSearch(x, y):
    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
        
        if 0 <= nx < 5 and 0 <= ny < 5:
            if room[nx][ny] == 'P':
                return 0
            elif room[nx][ny] == 'O':
                if secondSearch(nx, ny, x, y) == 0:
                    return 0

def secondSearch(x, y, start_x, start_y):
    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
        
        if 0 <= nx < 5 and 0 <= ny < 5  and (nx != start_x or ny != start_y):
            if room[nx][ny] == 'P':
                return 0
    return 1

오랜만에 푼 문제라 그런지 어렵진 않았지만 시간이 조금 걸린 문제였다.

전형적인 탐색 문제였지만 DFS, BFS를 사용하여 풀 수 도 있지만 맨해튼 거리가 2 이하에 응시자가 있는지

확인만 하면 되기 때문에 탐색 함수를 2번 호출해주면 된다.

 

첫번째 탐색할 때와 두 번째 탐색할 때 조건이 조금 다르게 때문에 함수를 따로 만들어 주었으며

탐색 도중 다른 응시자가 나오면 무조건 거리두기를 안 지켰다고 판단하고 break 해주었다.

첫 번째 탐색을 하고 만약 빈 공간이라면 해당 지점에서 두 번째 탐색을 진행하였다.

두 번째 탐색을 진행하고도 다른 응시자가 나오지 않으면 거리두기 지킨 것으로 판단하였다.

 

ps. 오랜만에 알고리즘 코딩을 해서 그런지 코드가 조금 지저분한 것 같다.

인턴 하느라 시간이 많이 부족하지만 그래도 하루에 하나씩은 푸는 걸 목표로 하고 있다.