프로그래머스_거리두기 확인하기

문제

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

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

풀이

 

이 문제는 DFS와 BFS 2가지 방법으로 모두 풀이 가능하다. 그래프의 크기가 5x5로 고정이기에 시간 초과 및 메모리 초과를 고려하지 않아도 된다.

 

깊이를 초과하지 않는 선에서 탐색을 진행한다. 

1. PP 패턴

2. POP 패턴

2가지가 나타나지 않으면 거리두기를 지키고 있다고 판단한다.

 

깊이 1

깊이 2

코드

# 5줄 5행 범위 내에 있는지 확인
check = lambda i, j : 0<=i<5 and 0<=j<5

def f(place) : 
    for i in range(5) : 
        for j in range(5) : 
            if place[i][j]=='P' : 
                stack = [(i, j, place[i][j])]

                while stack : 
                    mi, mj, m = stack.pop()
                    if m=='PP' : return 0
                    if m=='POP' : return 0

                    if len(m)<3 : # ↑, ←, ↓, →
                        for i_, j_ in [(mi-1, mj), (mi, mj-1), (mi+1, mj), (mi, mj+1)] : 
                            if check(i_, j_) and (i, j)!=(i_, j_) : 
                                stack.append((i_, j_, m+place[i_][j_]))
    return 1

def solution(places): 
    return [f(p) for p in places]