[pgs카카오 거리두기확인] DFS 심화문제

프로그래머스 거리두기확인하기 2021 카카오 코딩테스트

Question

Solution

advanced DFS

기본적인 DFS 문제와 다른 점을 파악해야 한다.

• 각 지점에서 DFS를 돌릴 때 visited map은 초기화 되어 있어야 한다. (=이미 파악했던 길을 다시 파악해야 하는 경우가 있다) 이 부분은 직접 이해를 해 보아야 한다. P1에서 DFS를 파악하면서 P2와 P3 근처의 길을 들렀다 하더라도 P2와 P3 간의 거리를 측정할 때는 다시 그 길을 지나봐야 한다.
• 한 차례의 DFS에서 연결된 모든 지점을 돌면 끝나는 것이 아니라, 다른 사람의 자리('P')를 만났을 때 출발 P와의 거리를 체크해야 한다. (=distance 값을 체크하고 있어야 한다)

PSEUDO

• [하나의 place를 체크하고 모든 place에 대해 답 구하기]
• 새로운 P에서 시작할 때 visited map을 매번 정의 (X만 못 가도록 visit 처리) (def build_visited_map)
• ans 1
• dfs_helper(root, distance, first_check)
• nonlocal visited_map, ans, place
• place에서 'P'이고 첫 시작점이 아니면(first_check != 0):
  distance <=2 이면 ans = 0, return (종료조건)
• togo는 0~4 가동 범위 내 + visited_map에서 False인 부분('O'나 'P' 중 안 가본 곳)
• for loc in togo:
  dfs_helper(loc, distance+1, first_check=1)
• 모든 P에서 시작해서 helper를 도는데 새로운 P에서 시작할 때마다 다시 visited map을 정의
  ans==0으로 바뀌면 전체 함수 바로 return 0

def solution(places: List[List]):

    def a_place(place):
        '하나의 대기실 체크'
        # 문제 생기면 바로 return 0
        ans = 1
        def build_visited():
            nonlocal place
            visited_map = [[False for i in range(5)] for j in range(5)]
            for i in range(5):
                for j in range(5):
                    if place[i][j] == 'X':
                        visited_map[i][j] = True
            return visited_map
            

        def dfs_helper(root, distance, first_check):
            nonlocal place, visited_map, ans
            i, j = root[0], root[1]
            visited_map[i][j] = True
            if place[i][j] == 'P' and first_check != 0:
                if distance <= 2:
                    ans = 0
                return
            
            togo = [(i+1,j), (i-1,j), (i,j+1), (i,j-1)]
            def check_loc(loc):
                nonlocal visited_map
                i, j = loc[0], loc[1]
                if i < 0 or i > 4: return False
                if j < 0 or j > 4: return False
                if visited_map[i][j]:
                    return False
                return loc
            togo = list(map(check_loc, togo))

            for loc in togo:
                if loc:
                    dfs_helper(loc, distance+1, 1)
        
        for i in range(5):
            for j in range(5):
                if place[i][j] == 'P':
                    visited_map = build_visited()
                    dfs_helper((i,j), 0, 0)
                    if ans == 0:
                        return 0
        return 1
    
    return [a_place(place) for place in places]

github