프로그래머스 [Lv. 3] [PCCP 기출문제] 4번 / 수레 움직이기 {언어 : Python}

문제 링크

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

프로그래머스

정답 코드

answer = 16
def solution(maze):
    n = len(maze)
    m = len(maze[0])
    
    dr = [-1, 1, 0, 0]
    dc = [0, 0, -1, 1]
    def isValid(nr, nc):
        return 0 <= nr < n and 0 <= nc < m
    
    redVisited = [[0] * m for _ in range(n)]
    blueVisited = [[0] * m for _ in range(n)]
    
    redStartRow, redStartCol, redEndRow, redEndCol = 0, 0, 0, 0
    blueStartRow, blueStartCol, blueEndRow, blueEndCol = 0, 0, 0, 0
    
    # rf, bf는 red finish, blue finish
    def move(who, rsr, rsc, bsr, bsc, rf, bf, rCnt, bCnt):
        global answer
        if max(rCnt, bCnt) > answer:
            return
        # 둘 다 도달했으면 
        if bf and rf:
            cnt = max(rCnt, bCnt)
            if answer > cnt:
                answer = cnt
            return
        
        # true면 red
        # red이고 red가 도착하지 못했다면
        if who and not rf:
            # 움직일 지점 탐색
            for d in range(4):
                rnr = rsr + dr[d]
                rnc = rsc + dc[d]
                if isValid(rnr, rnc):
                    # 만약 blue의 위치와 같다면
                    if (rnr, rnc) == (bsr, bsc):
                        continue
                    # 못 지나간다면
                    # 1. 이미 지나간 곳
                    if redVisited[rnr][rnc] == 1:
                        continue
                    # 2. blue가 도착했고 도착지점을 가려고 한다면
                    if bf and maze[rnr][rnc] == 4:
                        continue
                    # 3. 벽이라면
                    if maze[rnr][rnc] == 5:
                        continue
                    
                    # 이동 가능
                    redVisited[rnr][rnc] = 1
                    
                    # 도착지점이라면
                    if maze[rnr][rnc] == 3:
                        move(not who, rnr, rnc, bsr, bsc, True, bf, rCnt+1, bCnt)
                    elif not bf:
                        if rCnt+1 == bCnt:
                            move(not who, rnr, rnc, bsr, bsc, rf, bf, rCnt+1, bCnt)
                            move(who, rnr, rnc, bsr, bsc, rf, bf, rCnt+1, bCnt)
                        else:
                            move(not who, rnr, rnc, bsr, bsc, rf, bf, rCnt+1, bCnt)
                    else:
                        move(who, rnr, rnc, bsr, bsc, rf, bf, rCnt+1, bCnt)
                    
                    redVisited[rnr][rnc] = 0
                    
        # blue일 때
        else:
            for d in range(4):
                bnr = bsr + dr[d]     
                bnc = bsc + dc[d]
                if (isValid(bnr, bnc)):
                    # 만약 red의 위치와 같다면
                    if (bnr, bnc) == (rsr, rsc):
                        continue
                    # 못 지나간다면
                    # 1. 이미 지나간 곳
                    if blueVisited[bnr][bnc] == 1:
                        continue
                    # 2. red가 이미 도착했고 도착지점을 가려고 한다면
                    if rf and maze[bnr][bnc] == 3:
                        continue
                    # 3. 벽이라면
                    if maze[bnr][bnc] == 5:
                        continue
                    
                    # 이동 가능
                    blueVisited[bnr][bnc] = 1
                    
                    # 도착지점이라면
                    if maze[bnr][bnc] == 4:
                        move(not who, rsr, rsc, bnr, bnc, rf, True, rCnt, bCnt+1)
                    elif not rf:
                        if bCnt+1 == rCnt:
                            move(not who, rsr, rsc, bnr, bnc, rf, bf, rCnt, bCnt+1)
                            move(who, rsr, rsc, bnr, bnc, rf, bf, rCnt, bCnt+1)
                        else:
                            move(not who, rsr, rsc, bnr, bnc, rf, bf, rCnt, bCnt+1)
                    else:
                        move(who, rsr, rsc, bnr, bnc, rf, bf, rCnt, bCnt+1)
                        
                    blueVisited[bnr][bnc] = 0
    
    # 위치 찾기
    for r in range(n):
        for c in range(m):
            mrc = maze[r][c]
            if mrc == 0 or mrc == 5:
                continue
            elif mrc == 1:
                redStartRow, redStartCol = r, c
                redVisited[redStartRow][redStartCol] = 1
            elif mrc == 2:
                blueStartRow, blueStartCol = r, c
                blueVisited[blueStartRow][blueStartCol] = 1
            elif mrc == 3:
                redEndRow, redEndCol = r, c
            else:
                blueEndRow, blueEndCol = r, c
    
    
    move(True, redStartRow, redStartCol, blueStartRow, blueStartCol, False, False, 0, 0)
    move(False, redStartRow, redStartCol, blueStartRow, blueStartCol, False, False, 0, 0)
    
    if answer == 16:
        return 0
    return answer

풀이 방법

• 빨간색 수레 우선:
  • 빨간색 수레가 이동 가능한 위치로 가기 위해 주변을 탐색한다.
  • 만약 이동할 위치가 파란색 수레의 위치라면 건너뛴다.
  • 만약 이동할 위치가 도착 지점이라면, 도착 상태를 업데이트하고 다음 수레로 이동한다.
• 파란색 수레 우선:
  • 파란색 수레도 마찬가지로 주변을 탐색하며, 빨간색 수레와 같은 방식으로 이동한다.
• 이동 순서:
  1. 빨 -> 파 -> 파: 빨간색 수레가 먼저 움직이고, 다음에 파란색 수레가 두 번 움직일 수 있다.
  2. 빨 -> 파 -> 빨: 빨간색 수레가 먼저 움직이고, 파란색 수레가 그 뒤를 따르며, 마지막에 다시 빨간색 수레가 이동하할 수 있다.
  3. 빨 -> 빨 -> 파: 빨간색 수레가 두 번 연속으로 움직이고, 마지막에 파란색 수레가 이동하는 경로는 불가능하다.

느낀점

• 움직이기 전에 현재 지점의 방문체크를 안하는 실수를 했다...
• 다시봐야 하는 이유는 단지 위의 이유 때문이다...