프로그래머스 | Python | 단순구현 | 공원 산책 (Lv.1)

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

프로그래머스

 

 

이 문제는 시뮬레이션 문제로, 주어진 경로(routes)에 따라 로봇 강아지가 이동하는 것을 구현하는 문제입니다.

---

1️⃣ 핵심 개념 및 접근 방식

• 격자 이동: 2차원 배열(공원 park) 내에서 이동을 시뮬레이션해야 함.
• 조건 체크:
  1. 이동할 위치가 공원을 벗어나는지 확인
  2. 이동하는 경로 중 장애물('X')이 있는지 확인
  3. 위 조건 중 하나라도 만족하면 해당 명령은 무시하고 다음 명령을 수행
• 시작 지점(S) 찾기: 공원에서 S의 위치를 먼저 찾아야 함.

---

2️⃣ 코드 구현

def solution(park, routes):
    # 방향에 따른 좌표 이동량 설정 (딕셔너리 사용)
    move = {'N': (-1, 0), 'S': (1, 0), 'W': (0, -1), 'E': (0, 1)}

    # 공원의 크기
    H, W = len(park), len(park[0])

    # 시작 위치(S) 찾기
    for r in range(H):
        for c in range(W):
            if park[r][c] == 'S':
                x, y = r, c  # 시작 위치 저장
                break

    # 명령어 수행
    for route in routes:
        direction, step = route.split()
        step = int(step)

        # 이동 가능 여부 확인
        nx, ny = x, y  # 현재 위치 저장
        for _ in range(step):
            nx += move[direction][0]
            ny += move[direction][1]

            # 공원 범위 밖이면 무시
            if not (0 <= nx < H and 0 <= ny < W):
                break

            # 장애물(X) 만나면 무시
            if park[nx][ny] == 'X':
                break
        else:
            # 모든 조건을 만족하면 이동
            x, y = nx, ny

    return [x, y]

---

3️⃣ 코드 설명

1. 방향 딕셔너리 생성

• N: 위로 한 칸 이동 → (-1, 0)
• S: 아래로 한 칸 이동 → (1, 0)
• W: 왼쪽으로 한 칸 이동 → (0, -1)
• E: 오른쪽으로 한 칸 이동 → (0, 1)

---

2. 시작 위치(S) 찾기

for r in range(H):
    for c in range(W):
        if park[r][c] == 'S':
            x, y = r, c  # 시작 위치 저장
            break

• 2차원 배열을 탐색하여 'S'의 위치를 찾고 (x, y)에 저장

---

🔹 3. 경로(routes)를 순차적으로 처리

for route in routes:
    direction, step = route.split()
    step = int(step)

• 명령어 "E 2"를 direction='E', step=2로 분리
• step을 정수형(int)으로 변환하여 사용

---

🔹 4. 이동할 위치 확인

nx, ny = x, y  # 현재 위치 저장
for _ in range(step):
    nx += move[direction][0]
    ny += move[direction][1]

    # 공원 범위 밖이면 무시
    if not (0 <= nx < H and 0 <= ny < W):
        break

    # 장애물(X) 만나면 무시
    if park[nx][ny] == 'X':
        break
else:
    # 모든 조건을 만족하면 이동
    x, y = nx, ny

• 주어진 거리(step)만큼 미리 이동 가능 여부를 체크
• 이동 도중 범위를 벗어나거나('X') 장애물을 만나면 명령 무시
• for문이 break 없이 정상 종료된 경우만 x, y 업데이트

---

4️⃣ 예제 실행

✅ 예제 1

park = ["SOO", "OOO", "OOO"]
routes = ["E 2", "S 2", "W 1"]
print(solution(park, routes))  # [2, 1]

📝 과정

1. "E 2" → (0, 0) → (0, 2) (정상 이동)
2. "S 2" → (0, 2) → (2, 2) (정상 이동)
3. "W 1" → (2, 2) → (2, 1) (정상 이동) ✅ 최종 위치: [2, 1]

---

✅ 예제 2

park = ["SOO", "OXX", "OOO"]
routes = ["E 2", "S 2", "W 1"]
print(solution(park, routes))  # [0, 1]

📝 과정

1. "E 2" → (0, 0) → (0, 2) (정상 이동)
2. "S 2" → (0, 2) (장애물 X에 막혀 이동 실패)
3. "W 1" → (0, 2) → (0, 1) (정상 이동) ✅ 최종 위치: [0, 1]

---

5️⃣ 시간 복잡도 분석

• 시작 위치 탐색: O(N*M) (공원 크기만큼 탐색)
• 이동 처리: O(K) (K는 명령 개수, 최악의 경우 50)
• 총 시간 복잡도: O(N*M + K) ≈ O(N*M), (최대 2500이므로 충분히 빠름)

---

6️⃣ 정리

✅ 시뮬레이션 유형 문제

✅ 2차원 배열 내에서 이동하는 문제

✅ 공원 경계 및 장애물 검사 필요

✅ 이동 조건을 만족하면 최종 위치 반환