[프로그래머스] 미로탈출 명령어

문제링크 : https://school.programmers.co.kr/learn/courses/30/lessons/150365

💻 문제 풀이 : Python

⭐ 내 풀이 : 시간초과

globFlag = [0]
globAnswer = ""

def isPossible(x, y, r, c, k):
    dist = abs(x - r) + abs(y - c)
    if (dist - k) % 2 == 0:
        return True
    else:
        return False
    
def getDir(direction):
    if (direction == "d"):
        return 0
    elif (direction == "l"):
        return 1
    elif (direction == "r"):
        return 2
    elif (direction == "u"):
        return 3

# 움직이기
def move(x, y, n, m, road):
    dr = [1, 0, 0, -1]
    dc = [0, -1, 1, 0]
    
    for i in road:
        x += dr[getDir(i)]
        y += dc[getDir(i)]
        if (x > n) or (y > m) or (x <= 0) or (y <= 0):
            return -1, -1
    return x, y

# 경로 정하기
def makeRoad(k, road, dirList, depth, n, m, x, y, r, c):
    global globFlag, globAnswer
    
    if globFlag[0] == 1:
        return None
    
    if (depth == k):
        nextX, nextY = move(x, y, n, m, road)
        if (nextX == r) and (nextY == c):
            globFlag[0] = 1
            globAnswer = ''.join(road)
        return None
        
    for i in dirList:
        road.append(i)
        makeRoad(k, road, dirList, depth+1, n, m, x, y, r, c)
        road.pop()

def solution(n, m, x, y, r, c, k):
    global globFlag, globAnswer
    dirList = ["d", "l", "r", "u"]
    
    if isPossible(x, y, r, c, k) == False:
        return "impossible"
    
    road = []
    makeRoad(k, road, dirList, 0, n, m, x, y, r, c)
    print(globAnswer)
    
    if globFlag[0] == 1:
        return globAnswer
    else:
        return "impossible"

정답 풀이

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)

globFlag = [0]
globAnswer = []

def isValid(nx, ny, n, m):
    if (nx < 1) or (ny < 1) or (nx > n) or (ny > m):
        return False
    else:
        return True

def isPossible(x, y, r, c, k):
    dist = abs(x - r) + abs(y - c)
    if (dist > k):
        return False
    elif (dist - k) % 2 == 0:
        return True
    else:
        return False

def dfs(n, m, x, y, r, c, k, depth, road, direction):
    global globAnswer, globFlag
    if globFlag[0] == 1:
        return
    
    if (depth == k):
        if (x == r) and (y == c):
            globFlag[0] = 1
            globAnswer = road[:]
            print(road, globAnswer)
        return
    
    for dr, dc in direction:
        nr, nc = x + dr, y + dc
        if (isValid(nr, nc, n, m) and isPossible(nr, nc, r, c, k - depth - 1)):
            road.append(direction[(dr, dc)])
            dfs(n, m, nr, nc, r, c, k, depth+1, road, direction)
            road.pop()
        
    
def solution(n, m, x, y, r, c, k):
    global globAnswer
    road = []
    answer = ''
    
    if not isPossible(x, y, r, c, k):
        return "impossible"
    
    direction = {(1, 0):"d", (0, -1):"l", (0, 1):"r", (-1, 0):"u"}
    dfs(n, m, x, y, r, c, k, 0, road, direction)
    answer = ''.join(globAnswer)
    return answer

---

📌 memo

파이썬 dfs 풀 때 필요 라이브러리

import sys

sys.setrecursionlimit(10**8)

배열 복사

to = from[:]

dict로 방향배열 만들기

direction = {(1, 0) : "d", (0, -1):"l", (0, 1):"r", (-1, 0):"u"}

탐색 전 조건 고려하기

1. 정답을 찾았으면 더 이상 탐색하지 않기!
2. 다음 방향을 고려할 때, 불가능 할 지 판단 후 이동하기!
3. 직관적으로 고려하면, answer로 방향을 만들고, 이동하여 판단해도 됨. 그러나 시간이 두 배로 걸림!
   => 이동하면서 판단하고, 정답 배열에 반영만 하는 편이 빠름!