안녕하세요, Will 입니다.
오늘은 프로그래머스 문제인 ''공원 산책" 문제 풀이를 가져왔습니다.
Map과 이동에 관련된 문제를 풀 때 접근하는 방법을 정리하고자 이 글을 작성합니다.
문제
지나다니는 길을 'O', 장애물을 'X'로 나타낸 직사각형 격자 모양의 공원에서 로봇 강아지가 산책을 하려합니다. 산책은 로봇 강아지에 미리 입력된 명령에 따라 진행하며, 명령은 다음과 같은 형식으로 주어집니다.
["방향 거리", "방향 거리" … ]
예를 들어 "E 5"는 로봇 강아지가 현재 위치에서 동쪽으로 5칸 이동했다는 의미입니다. 로봇 강아지는 명령을 수행하기 전에 다음 두 가지를 먼저 확인합니다.
주어진 방향으로 이동할 때 공원을 벗어나는지 확인합니다.
주어진 방향으로 이동 중 장애물을 만나는지 확인합니다.
위 두 가지중 어느 하나라도 해당된다면, 로봇 강아지는 해당 명령을 무시하고 다음 명령을 수행합니다.
공원의 가로 길이가 W, 세로 길이가 H라고 할 때, 공원의 좌측 상단의 좌표는 (0, 0), 우측 하단의 좌표는 (H - 1, W - 1) 입니다.
공원을 나타내는 문자열 배열 park, 로봇 강아지가 수행할 명령이 담긴 문자열 배열 routes가 매개변수로 주어질 때, 로봇 강아지가 모든 명령을 수행 후 놓인 위치를 [세로 방향 좌표, 가로 방향 좌표] 순으로 배열에 담아 return 하도록 solution 함수를 완성해주세요.
제한사항
3 ≤ park의 길이 ≤ 50
3 ≤ park[i]의 길이 ≤ 50
park[i]는 다음 문자들로 이루어져 있으며 시작지점은 하나만 주어집니다.
S : 시작 지점
O : 이동 가능한 통로
X : 장애물
park는 직사각형 모양입니다.
1 ≤ routes의 길이 ≤ 50
routes의 각 원소는 로봇 강아지가 수행할 명령어를 나타냅니다.
로봇 강아지는 routes의 첫 번째 원소부터 순서대로 명령을 수행합니다.
routes의 원소는 "op n"과 같은 구조로 이루어져 있으며, op는 이동할 방향, n은 이동할 칸의 수를 의미합니다.
op는 다음 네 가지중 하나로 이루어져 있습니다.
N : 북쪽으로 주어진 칸만큼 이동합니다.
S : 남쪽으로 주어진 칸만큼 이동합니다.
W : 서쪽으로 주어진 칸만큼 이동합니다.
E : 동쪽으로 주어진 칸만큼 이동합니다.
1 ≤ n ≤ 9
입출력 예시
| park | routes | result |
| ["SOO","OOO","OOO"] | ["E 2","S 2","W 1"] | [2,1] |
| ["SOO","OXX","OOO"] | ["E 2","S 2","W 1"] | [0,1] |
입출력 예 #1
입력된 명령대로 동쪽으로 2칸, 남쪽으로 2칸, 서쪽으로 1칸 이동하면 [0,0] -> [0,2] -> [2,2] -> [2,1]이 됩니다.
입출력 예 #2
입력된 명령대로라면 동쪽으로 2칸, 남쪽으로 2칸, 서쪽으로 1칸 이동해야하지만 남쪽으로 2칸 이동할 때 장애물이 있는 칸을 지나기 때문에 해당 명령을 제외한 명령들만 따릅니다. 결과적으로는 [0,0] -> [0,2] -> [0,1]이 됩니다.
풀이
풀고보니 이 문제는 3가지 과정으로 나뉜다.
1. 초기 위치 찾기
2. 검색하기
3. 이동 시키기
1. 초기 위치 찾기
초기 위치는 주어진 park 내부에 존재하는 'S'의 위치를 찾는 것이다.
|
1
2
3
4
5
6
7
8
9
10
|
def solution(park, routes):
C,R,r,c = len(park),len(park[0]),0,0
move = {'E':(0,1),'W':(0,-1),"S":(1,0),'N':(-1,0)}
print('C: {} R: {}'.format(C,R))
for i_index,i in enumerate(park):
for j_index,j in enumerate(i):
if j == 'S':
r=j_index
c=i_index
print('첫 포지션: {},{}'.format(c,r))
|
cs |
c는 column, r은 row를 의미한다. move는 추후 검색 시 사용하기 위해 만들어둔 dic이니 지금은 신경쓰지 않아도 된다.
C, R(대문자)는 최대 길이 검색 시 활용하기 위해 만들어 두었다.
line 5: 먼저 park list 내의 문자열 값을 차례로 가져오고
line 6: 해당 문자열 내의 문자를 차례로 가져와서
line 7~9: 해당 값이 'S'이면, 초기 위치로 정한다.
*참고) 문제를 보면 (h,w) 좌표로 표시가 되므로, x,y 좌표로 표현하면 (y,x)가 된다.
2. 검색하기, 3. 이동 시키기
초기 위치를 찾았으니 이제 이동을 시켜보자.
그런데 이동할 수 있는지 먼저 확인(검색)을 해보아야 한다.
문제의 조건은
이동 후 도착 지점이 (1) 최대 길이를 넘지 않으며, // 지도 밖으로는 이동 할 수 없다.
이동 과정 내에 (2) 'X' 지점이 없어야 한다. // 장애물이 있으면 이동 할 수 없다.
>>조건에 부합하지 않으면 해당 명령은 무시한다.
아래 코드를 보자.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
for route in routes:
print('이동 전 포지션: {},{}'.format(c,r))
new_r, new_c = r,c
dc,dr=move[route[0]]
print('dc,dc: {},{}'.format(dc,dr))
for i in range(int(route[2])):
if 0 <= new_r+dr < R and 0 <= new_c+dc < C and park[new_c+dc][new_r+dr] != 'X':
print('조건 통과')
new_r += dr
new_c += dc
else:
print('조건 통과 못함')
new_r,new_c = r,c
break
r=new_r
c=new_c
|
cs |
line1: 먼저 routes는 'E 2'와 같은 방향, 이동거리가 담긴 list이다.
routes에 담긴 route 수 만큼 '이동'이 수행되므로 for문을 사용하여 route를 가져왔다.
line 3: new_r, new_c는 도착 지점의 위치를 나타내기 위해 만든 변수이다.
line 4: dc, dr은 이동할 양을 의미한다. 위에서 만든 move dictionary가 여기서 사용된다.
route[0]은 'E', 'S' 등의 방향을 의미하는 문자열이다.
ex) 'E'의 경우 dc:0, dr:1
line 6~7: 검색을 진행한다. 검색은 1칸 씩 이동 될 때마다 진행되게 하였다.
(1) 0 <= new_r+dr < R and 0 <= new_c+dc
new_r+dr은 row 상으로 이동 된 위치이다. 1칸 이동 된 위치가 지도 밖인지 확인한다.
0보다 작으면 지도 왼쪽 밖으로, R과 같으면 오른쪽 밖으로 이동된 것이다.
(2) park[new_c+dc][new_r+dr] != 'X'
park[new_c+dc][new_r+dr]는 이동된 위치의 park 값이다. 해당 값이 'X'이면 장애물이 되므로
X가 아닐 경우에만 이동하도록 하였다.
line 9~14: 조건에 부합할 경우 이동을 시키고, 한번이라도 조건에 맞지 않으면 기존 위치로 초기화한다.
line 15~16: 이동 완료된 위치를 기본 위치로 변경한다.
느낀 점
알고리즘 공부를 하며 기본적인 Map 문제에도 턱턱 막히는 걸 보니.. 아직 멀었다고 느껴진다.
그래도 프로그래머스 문제를 차근차근 풀며 실력이 늘어감을 느낀다.
지도 문제는 Map이 list로 주어지고, 주어지지 않으면 list로 만들어 보자.
검색은 지도 크기, 장애물 등의 조건이 빠지지 않도록 신경써서 코드를 짜도록 하자.
'프로그래머스' 카테고리의 다른 글
| 프로그래머스 - 달리기 경주 풀이(Python) (0) | 2023.04.29 |
|---|---|
| 프로그래머스 타겟넘버 C# DFS (0) | 2022.04.29 |