PostsSeriesLabsAlgo

백트래킹·구현

시뮬레이션

시키는 대로 그대로 하기

로봇에게 명령 줄이 주어졌습니다. 다 하고 나면 처음 칸에서 몇 칸 떨어질지 먼저 고르고, 명령을 한 글자씩 대신 실행해 보세요.

방에 로봇(▲)이 서 있어요. 명령 줄을 한 글자씩 따라 해요. F 는 앞으로 한 칸 가고, R 은 오른쪽으로, L 은 왼쪽으로 90도 돌아요. 명령 8개를 다 하고 나면 로봇은 처음 칸에서 몇 칸 떨어져 있을까요?

FFRFFLFF

끝낸 명령 0 / 8

내 예상 칸 · 실제 4칸 → 달랐어요

(3, 0) → (2, 0) → (1, 0) → (1, 1) → (0, 1)명령 8개 중 F 2번은 막혀서 제자리였습니다. 막히지 않았다면 6칸 떨어진 곳에 섰을 텐데, 실제로는 4칸입니다.

  • 한 글자씩 그대로 — 명령이 시키는 일을 규칙대로 하나씩 따라 했다
  • 막히면 — 앞 칸이 벽이든 방 바깥이든 로봇은 제자리에 섰다
  • 돌기는 — 칸은 그대로고 방향만 바뀌었다

규칙을 한 단계씩 그대로 따라 하며 결과를 구하는 방법 = 시뮬레이션(simulation)

방향 네 개를 숫자 두 줄(dr, dc)로 두면 앞 칸은 r + dr[d], 돌기는 d = (d + 1) % 4 한 줄입니다. 이 숫자 두 줄 = 델타 배열

앞 칸이 막혔는지는 움직이기 전에 본다

  • 방금 겪은 막힘 — 5번째 명령은 벽에, 8번째 명령은 방 바깥에 막혔다. 둘 다 제자리였다
  • 순서 — 앞 칸을 먼저 계산하고, 갈 수 있는 칸인지 보고, 그다음에 움직인다
  • 움직인 뒤에 보면 — 로봇이 벽 안에 들어가 있다. 벽은 지나갈 수 없다

코드는 규칙을 한 줄씩 그대로 옮긴 것이다

위에서 한 것과 같은 방, 같은 명령입니다. (r, c) 는 위에서 r번째 줄, 왼쪽에서 c번째 칸이고 0부터 셉니다. d 는 방향이고 0 위, 1 오른쪽, 2 아래, 3 왼쪽입니다.

다음을 눌러 한 줄씩 넘기며 명령 줄과 로봇을 보세요.

로봇 (3, 0) 칸 · ▲ 위를 봄

다음을 눌러 한 줄씩 넘겨 보세요

r = 3 c = 0 d = 0

robot.py
  1. 1def robot(commands, grid, r, c):
  2. 2 rows, cols = len(grid), len(grid[0])
  3. 3 dr = [-1, 0, 1, 0]
  4. 4 dc = [0, 1, 0, -1]
  5. 5 d = 0
  6. 6 for cmd in commands:
  7. 7 if cmd == "F":
  8. 8 nr, nc = r + dr[d], c + dc[d]
  9. 9 if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 0:
  10. 10 r, c = nr, nc
  11. 11 elif cmd == "R":
  12. 12 d = (d + 1) % 4
  13. 13 else:
  14. 14 d = (d - 1) % 4
  15. 15 return r, c
0 / 29
  • dr·dc — d 방향으로 한 칸 갈 때 행·열이 얼마나 바뀌는지. 위(0)는 행이 −1이다
  • 0 <= nr < rows … — 앞 칸이 방 안이고 빈 칸일 때만 참이다. 거짓이면 10번 줄을 건너뛴다
  • d = (d + 1) % 4 — 오른쪽으로 돌기. 3 다음은 다시 0이 된다

명령 F F R F F L F F 에서 가운데 L 을 R 로 바꾸면 로봇은 어느 칸에 설까요?

시뮬레이션에서 틀리는 자리

  • (행, 열)과 (x, y)를 섞는다 — 위로 가면 행이 줄어든다(dr[0] = -1). x, y 로 생각하면 위아래가 뒤집힌다
  • 경계 검사를 빼면 — 위·왼쪽 바깥은 에러 없이 grid[-1] 로 반대편 줄을 읽는다. 이 방에서 (0, 1) 대신 (-1, 1) 에 섰다. 오른쪽·아래 바깥은 IndexError: list index out of range 가 난다
  • 방향 순서를 문제와 맞춘다 — 위, 오른쪽, 아래, 왼쪽이 시계 방향이다. 왼쪽과 오른쪽 자리를 바꾸면 같은 명령이 (0, 0) 에서 끝났다
  • (d - 1) % 4 는 — 파이썬은 3이 나온다. 다른 언어는 -1 이 나온다. 그래서 (d + 3) % 4 로 쓰기도 한다
  • [[0] * 5] * 5 로 방을 만들면 — 행이 전부 같은 리스트다. 한 칸에 벽을 세우면 모든 줄의 같은 열이 벽이 된다. [[0] * 5 for _ in range(5)] 로 만든다

문제에서 이 말이 보이면

규칙이 길게 주어진다격자 위에서 이동한다시키는 대로 구현

다음 장에서는 뒤집어도 같은 말인지 확인하는 문자열과 회문을 봅니다.