프로그래머스 [Lv. 3] 사라지는 발판 {언어 : Python} [다시 풀어 보기]

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/92345

프로그래머스

정답 코드

def solution(board, aloc, bloc):
    n, m = len(board), len(board[0])
    ar, ac = aloc
    br, bc = bloc
    
    dr = [-1, 1, 0, 0]
    dc = [0, 0, -1, 1]    
    def isValid(nr, nc):
        return 0 <= nr < n and 0 <= nc < m
    
    def dfs(ar, ac, br, bc, visited):
        if (ar, ac) in visited:
            return 0
        aCnt = 0
        for d in range(4):
            nr = ar + dr[d]
            nc = ac + dc[d]
            if isValid(nr, nc) and (nr, nc) not in visited and board[nr][nc] == 1:
                bCnt = dfs(br, bc, nr, nc, visited + [(ar, ac)]) + 1
            
                if aCnt % 2 == 0:
                    if bCnt % 2:
                        aCnt = bCnt
                    else:
                        aCnt = max(aCnt, bCnt)
                else:
                    if bCnt % 2:
                        aCnt = min(aCnt, bCnt)
        return aCnt
    answer = dfs(ar, ac, br, bc, [])
    return answer

풀이 방법

 

1. 초기 세팅:
   • board는 발판 배열이고, aloc과 bloc은 각각 플레이어 A와 B의 시작 위치이다.
   • dr와 dc는 각각 상하좌우 이동 방향을 나타내는 배열이다.
2. isValid 함수:
   • 주어진 위치가 보드 내에 있고 발판이 있는지 확인한다.
3. DFS 함수 (dfs):
   • dfs 함수는 두 플레이어의 위치(ar, ac와 br, bc)와 visited라는 방문한 위치를 인자로 받는다.
   • 현재 위치가 이미 visited에 있으면 움직일 수 없기 때문에 0을 반환한다.
4. DFS 탐색 과정:
   • 현재 위치에서 상하좌우로 이동 가능한 위치를 확인하며, 이동할 수 있는 모든 경우를 dfs로 재귀 호출한다.
   • 이동 가능한 경우, 상대 플레이어의 위치와 현재 위치를 바꿔 재귀적으로 dfs를 호출하고 그 결과에 1을 더해 이동 횟수를 계산한다.
5. 최적 경로 선택:
   • aCnt는 현재 플레이어의 최대 이동 횟수이다.
   • 현재 플레이어의 이동 횟수 aCnt와 상대의 이동 횟수 bCnt를 통해 짝수/홀수 조건을 나눠 최적의 값을 선택한다.

 

 

느낀점

• bfs로도 풀 수 있을 것 같은데 JavaScript로 다음엔 bfs로 풀어봐야겠다.