[프로그래머스] PCCP 기출문제 4번, 수레 움직이기

 

 

문제

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

프로그래머스

 

 

제가 복잡해하는 유형입니다. 동시에 여러개의 타겟이 움직일 수 있는 형태요 ㅎ

 

문제에서 '최소 혹은 최대의 경우를 구해봐라' 라고 나온다면, 보통 백트래킹으로 모든 경우를 체크해가며 최소인 경우를 찾으려 하는 것 같습니다.

추가로 구하려는 값이 최소라면, 현재 구해진 답보다 큰 값이 나오고 아직 구해야 할 연산들이 남아 있다면 더 체크를 해주지 않아도 되는 것이 백트래킹의 기본 아이디어이기도 합니다!

 

이 문제에서는 백트래킹 재귀의 조건을 세가지로 나눕니다.

 

1. red만 답에 도착해있는 경우

2. blue만 답에 도착해 있는 경우

3. 둘다 답에 도착하지 않은 경우

 

1, 2 조건에서는 단순하게 움직여주고 이동할 x, y가 범위에서 벗어나는지와 겹치는지를 체크해주면 되고,

3조건에서는 특별히, 서로의 값이 동시에 바뀌는 경우!

즉 아래와 같이 1, 2가 동시에 서로 위치를 바꾸는 경우를 추가해서 체크해주면 풀 수 있게 됩니다ㅎ

0 0 1 2 0 0 -> 0 0 2 1 0 0

 

 

answer = 1e9


def solution(maze):
    global answer
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    redStart = []
    blueStart = []
    redEnd = []
    blueEnd = []
    row = len(maze)
    col = len(maze[0])
    redVisited = [[0 for _ in range(len(maze[0]))] for _ in range(len(maze))]
    blueVisited = [[0 for _ in range(len(maze[0]))] for _ in range(len(maze))]

    for i in range(len(maze)):
        for j in range(len(maze[0])):
            if maze[i][j] == 1:
                redStart = [i, j]
            elif maze[i][j] == 2:
                blueStart = [i, j]
            elif maze[i][j] == 3:
                redEnd = [i, j]
            elif maze[i][j] == 4:
                blueEnd = [i, j]

    redVisited[redStart[0]][redStart[1]] = 1
    blueVisited[blueStart[0]][blueStart[1]] = 1

    def recursion(redCur, blueCur, cnt):
        global answer
        if redCur == redEnd and blueCur == blueEnd:
            answer = min(answer, cnt)
            return
        if cnt >= answer:
            return

	# red는 도착점에 있고, blue는 아직 도착하지 못한 상태
        if redCur == redEnd and blueCur != blueEnd:
            for i in range(4):
                bx = blueCur[0] + dx[i]
                by = blueCur[1] + dy[i]
                if bx < 0 or bx >= row or by < 0 or by >= col or blueVisited[bx][by] == 1 or maze[bx][by] == 5:
                    continue
                if redCur == [bx, by]:
                    continue
                blueVisited[bx][by] = 1
                recursion(redCur, [bx, by], cnt + 1)
                blueVisited[bx][by] = 0

	# red는 아직 도착하지 못했고, blue는 도착한 상태
        elif redCur != redEnd and blueCur == blueEnd:
            for i in range(4):
                rx = redCur[0] + dx[i]
                ry = redCur[1] + dy[i]
                if rx < 0 or rx >= row or ry < 0 or ry >= col or redVisited[rx][ry] == 1 or maze[rx][ry] == 5:
                    continue
                if [rx, ry] == blueCur:
                    continue
                redVisited[rx][ry] = 1
                recursion([rx, ry], blueCur, cnt + 1)
                redVisited[rx][ry] = 0

	# red, blue 둘다 도착하지 못한 상태
        else:
            for i in range(4):
                rx = redCur[0] + dx[i]
                ry = redCur[1] + dy[i]
                if rx < 0 or rx >= row or ry < 0 or ry >= col or redVisited[rx][ry] == 1 or maze[rx][ry] == 5:
                    continue
                for j in range(4):
                    bx = blueCur[0] + dx[j]
                    by = blueCur[1] + dy[j]
                    if bx < 0 or bx >= row or by < 0 or by >= col or blueVisited[bx][by] == 1 or maze[bx][by] == 5:
                        continue
                    if [rx, ry] == [bx, by] or ([rx, ry] == blueCur and [bx, by] == redCur):
                        continue
                    redVisited[rx][ry] = 1
                    blueVisited[bx][by] = 1
                    recursion([rx, ry], [bx, by], cnt + 1)
                    redVisited[rx][ry] = 0
                    blueVisited[bx][by] = 0

    recursion(redStart, blueStart, 0)
    if answer == 1e9:
        return 0

    return answer