[프로그래머스 Lv2/Python] 미로 탈출 명령어(구현/BFS)

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

문제 설명

n x m 격자 미로가 주어집니다. 당신은 미로의 (x, y)에서 출발해 (r, c)로 이동해서 탈출해야 합니다.

단, 미로를 탈출하는 조건이 세 가지 있습니다.

1. 격자의 바깥으로는 나갈 수 없습니다.
2. (x, y)에서 (r, c)까지 이동하는 거리가 총 k여야 합니다. 이때, (x, y)와 (r, c)격자를 포함해, 같은 격자를 두 번 이상 방문해도 됩니다.
3. 미로에서 탈출한 경로를 문자열로 나타냈을 때, 문자열이 사전 순으로 가장 빠른 경로로 탈출해야 합니다.

이동 경로는 다음과 같이 문자열로 바꿀 수 있습니다.

• l: 왼쪽으로 한 칸 이동
• r: 오른쪽으로 한 칸 이동
• u: 위쪽으로 한 칸 이동
• d: 아래쪽으로 한 칸 이동

예를 들어, 왼쪽으로 한 칸, 위로 한 칸, 왼쪽으로 한 칸 움직였다면, 문자열 "lul"로 나타낼 수 있습니다.

미로에서는 인접한 상, 하, 좌, 우 격자로 한 칸씩 이동할 수 있습니다.

예를 들어 다음과 같이 3 x 4 격자가 있다고 가정해 보겠습니다.

.... ..S. E...

미로의 좌측 상단은 (1, 1)이고 우측 하단은 (3, 4)입니다. .은 빈 공간, S는 출발 지점, E는 탈출 지점입니다.

탈출까지 이동해야 하는 거리 k가 5라면 다음과 같은 경로로 탈출할 수 있습니다.

1. lldud
2. ulldd
3. rdlll
4. dllrl
5. dllud
6. ...

이때 dllrl보다 사전 순으로 빠른 경로로 탈출할 수는 없습니다.

격자의 크기를 뜻하는 정수 n, m, 출발 위치를 뜻하는 정수 x, y, 탈출 지점을 뜻하는 정수 r, c, 탈출까지 이동해야 하는 거리를 뜻하는 정수 k가 매개변수로 주어집니다. 이때, 미로를 탈출하기 위한 경로를 return 하도록 solution 함수를 완성해주세요. 단, 위 조건대로 미로를 탈출할 수 없는 경우 "impossible"을 return 해야 합니다.

---

제한사항

• 2 ≤ n (= 미로의 세로 길이) ≤ 50
• 2 ≤ m (= 미로의 가로 길이) ≤ 50
• 1 ≤ x ≤ n
• 1 ≤ y ≤ m
• 1 ≤ r ≤ n
• 1 ≤ c ≤ m
• (x, y) ≠ (r, c)
• 1 ≤ k ≤ 2,500

---

입출력 예

n m x y r c k result

3	4	2	3	3	1	5	"dllrl"
2	2	1	1	2	2	2	"dr"
3	3	1	2	3	3	4	"impossible"

---

입출력 예 설명

입출력 예 #1

문제 예시와 동일합니다.

입출력 예 #2

미로의 크기는 2 x 2입니다. 출발 지점은 (1, 1)이고, 탈출 지점은 (2, 2)입니다.

빈 공간은 ., 출발 지점을 S, 탈출 지점을 E로 나타내면 다음과 같습니다.

S. .E

미로의 좌측 상단은 (1, 1)이고 우측 하단은 (2, 2)입니다.

탈출까지 이동해야 하는 거리 k가 2이므로 다음과 같은 경로로 탈출할 수 있습니다.

1. rd
2. dr

"dr"이 사전 순으로 가장 빠른 경로입니다. 따라서 "dr"을 return 해야 합니다.

입출력 예 #3

미로의 크기는 3 x 3입니다. 출발 지점은 (1, 2)이고, 탈출 지점은 (3, 3)입니다.

빈 공간은 ., 출발 지점을 S, 탈출 지점을 E로 나타내면 다음과 같습니다.

.S. ... ..E

미로의 좌측 상단은 (1, 1)이고 우측 하단은 (3, 3)입니다.

탈출까지 이동해야 하는 거리 k가 4입니다. 이때, 이동 거리가 4이면서, S에서 E까지 이동할 수 있는 경로는 존재하지 않습니다.

따라서 "impossible"을 return 해야 합니다.

 

---

[다른 사람의 풀이]

 

※ 풀이 전략

- 문제 자체를 완벽히 이해하고, 문제에 맞는 케이스를 1가지 케이스로 명확하게 풀어낸 풀이 

- 창의력 문제에 가까운 듯 하다. 나도 한 가지의 케이스로 명확히 한 후 구현하려고 했는데, 코드를 쓰면서도 헷갈렸다. 이렇게 푸는 문제가 나올 수 있다고? 하면서. 이런 문제도 출제될 수 있구나... 더 노력해볼 걸. 

def solution(n, m, x, y, r, c, k):
    answer = ''
    #x,y -> r,c 
    #좌상단이 1,1/ 우하단이 n,m
    #세로,가로  -> 2.3이 S
    diff = abs(x-r)+abs(y-c)
    if diff%2!=k%2 or diff>k:
        return 'impossible'
    #dlru 순서 

    rest = k-diff
    lcount = 0
    rcount = 0
    dcount = 0
    ucount = 0
    if x<r : #내려가야함
        dcount = r-x
    else:
        ucount = x-r
    if y<c :
        rcount = c-y
    else:
        lcount = y-c

    dplus = min( n-max(x,r), rest//2)
    rest -= dplus*2

    lplus = min( min(y,c)-1, rest//2)
    rest -= lplus*2

    answer = 'd'*(dcount+dplus)+'l'*(lcount+lplus)+'rl'*(rest//2)+'r'*(rcount+lplus)+'u'*(dplus+ucount)
    print(lcount,lplus,rcount,rest)



    return answer

 

※ 중요 포인트

- 문제 핵심을 파악했다면, 그냥 구현문제. 

---

[다른 사람의 풀이]

※ 풀이 전략

-

맨허튼 거리라는 게 있구나

-

홀수/짝수 외에도, 남은 거리보다 k보다 큰 경우 impossible. (당연한 건데 이 조건을 생각 못했다)

-

bfs 로 풀어도 통과되는구나 ... 다양한 가능성을 봐야되는데, 한 가지의 경우로 딱 구할 수 있는 줄 알았다. (n이 빠듯해서) 카카오라서 실제로 bfs로 풀면 통과 못할 줄 알았다. 근데 통과되는구나. 

from collections import deque

def solution(n, m, x, y, r, c, k):
    answer = ''
    # 남은 거리 탐색 자주 해주어야 하므로 함수로 빼주기
    def manhattan(x1, y1):
        return abs(x1 - (r-1)) + abs(y1-(c-1))

    # k가 최단 거리보다 작거나, 최단 거리 - k가 홀수라면 도착지에 k번만에 도착 불가
    if manhattan(x-1, y-1) > k or (manhattan(x-1, y-1) - k) % 2:
        return 'impossible'
    # 탐색 방향 사전순으로 - d l r u
    direct = {(1,0):'d', (0,-1):'l', (0,1):'r', (-1,0):'u'}
    q = deque()
    q.append((x-1, y-1, 0, ''))
    while q:
        si, sj, cnt, route = q.popleft()
        # 도착했는데 남은 거리가 홀수라면 도착지에 k만큼 오지 못한다!
        if (si, sj) == (r-1, c-1) and (k-cnt) % 2:
            return 'impossible'
        elif (si, sj) == (r-1, c-1) and cnt == k:
            return route
        for di, dj in direct:
            ni, nj = si+di, sj+dj
            if 0<=ni<n and 0<=nj<m:
                # 다음 이동 자리를 보는 것이므로 +1 을 해주어야 함
                if manhattan(ni, nj) + cnt + 1 > k:
                    continue
                q.append((ni, nj, cnt+1, route+direct[(di, dj)]))
                break

    return answer

 

※ 중요 포인트

-

for di, dj in direct: 로 하면 direct는 딕셔너리의 키 값만 가져와서 di, dj = key 이렇게 대입된다. 

-

방향을 이렇게 설정할 수도 있구나, direct = {(1,0):'d', (0,-1):'l', (0,1):'r', (-1,0):'u'}

난 항상 dx, dy만 써서 어떤게 동, 서, 남, 북인지 확실하지 않았었는데 이렇게 작성하면 적용할 때도 편하고(키 값만 가져올 수 있다니!), 각각 값의 방향이 명확하게 드러나니까 이렇게 활용하는 법