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

---

문제설명

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

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

사고과정

• 문제를 풀기 위해서 크게 DFS 탐색을 활용해서 구현했다. 
• 그리고 places가 주어지는 대기실 경우의 수들이 들어있으니 이것을 하나씩 loop를 돌면서 P(응시자) 좌표를 리스트에 넣는다. 그리고 응시자들 좌표 개수 중에 2개를 고르는 조합의 경우의 수를 모두 탐색하면서 한 조합 당 맨헤튼 거리가 2 초과면 pass, 만약 맨헤튼 거리가 2 이하인데, 파티션이 존재하는 경우에도 해당하지 않으면 바로 flag 값을 False로 바꾸고 컷-엣지하도록 설정했다. 만약 모든 조합의 경우의 수를 탐색했을 때, 거리두기를 모두 다 잘 지켰으면 flag 값은 True일 것이다.
• 각 place 마다 flag 값이 True일지, False일지에 따라 결과값 리스트에 1(거리두기 지켜짐), 0(못 지킴)을 append 해준다.

풀이

def dfs(L, s, n, p, res, place):
    global flag
    if not flag:
        return
    if L == 2:
        x1, y1 = res[0][0], res[0][1]
        x2, y2 = res[1][0], res[1][1]
        dist = abs(x1-x2) + abs(y1-y2)
        if dist <= 2:
            if x1 == x2: # 행이 같을 경우
                if place[x1][y2-1] != 'X':
                    flag = False
                    return
            elif y1 == y2: # 열이 같을 경우
                if place[x2-1][y1] != 'X':
                    flag = False
                    return
            else:
                if place[x1][y2] != 'X' or place[x2][y1] != 'X':
                    flag = False
                    return
    else:
        for i in range(s, n):
            res[L] = p[i]
            dfs(L+1, i+1, n, p, res, place)

flag = True

def solution(places):
    global flag
    answer = []
    for place in places:
        # 하나의 맵 정보
        p = []  # 참여자 위치
        for i in range(len(place)):
            for j in range(len(place[0])):
                if place[i][j] == 'P':
                    p.append((i, j))
        flag = True
        if not p:
            answer.append(1)
        else:
            res = [0] * 2
            dfs(0, 0, len(p), p, res, place)
            if flag:
                answer.append(1)
            else:
                answer.append(0)

    return answer