[코테] dx, dy 테크닉(3)

in Study / Coding Test

dx,dy 테크닉

  • dx, dy 테크닉을 이용해 격자에서의 이동을 간결하게 구현하는 방법을 배움

조건에 따라 방향이 변하는 경우

  • 격자 끝에 도착하면 방향을 반대로 뒤집어주어야 할 때, 숫자 3에서 현재 방향 번호를 빼준다.
    image
    • dir_num에서 0번과 3번이 반대 방향이 되도록 하고, 1번과 2번이 반대 방향이 되도록 하면, dir_num = dir_num - 3은 반대 방향으로 전환해준다.

방향이 문자로 주어진 경우

  • 움직여야 할 방향이 ‘R’, ‘D’, ‘U’, ‘L’과 같이 문자로 주어진 경우, if문이 아닌 dict 타입을 사용하면 좋다.
    • dict : 값을 key-value 형태로 저장할 수 있다. dict의 key로 string, int 등 다양한 type이 올 수 있다.
    # dict 초기화
d = {}

d['R'] = 0
d['D'] = 1
d['U'] = 2
d['L'] = 3

print(d['L']) # 3
print(d['D']) # 1

# dict를 값과 함께 초기화
d2 = {
    'A' : 3,
    'B' : '343'
}

print(d2['B']) # 343

  • dict를 이용하여 움직여야 할 방향을 코드로 나타내보기

    dxs, dys = [0, 1, -1, 0], [1, 0, 0, -1]
mapper = {
    'R': 0,
    'D': 1,
    'U': 2,
    'L': 3
}

c_dir = 'D'
move_dir = mapper[c_dir]

x, y = 0, 0
nx, ny = x + dxs[move_dir], y + dys[move_dir]


문제

image
image
image

입력 형식

첫 번째 줄에는 격자의 크기를 나타내는 n과 시간 t가 공백을 사이에 두고 주어집니다.
두 번째 줄에는 구슬 정보 (r, c, d)가 공백을 사이에 두고 주어집니다. 현재 구슬이 r행 c열에 놓여 있으며, d방향을 바라보고 있음을 뜻합니다. d는 위 아래 오른쪽 왼쪽을 의미하는 ‘U’, ‘D’, ‘R’, ‘L’ 4개의 문자 중 하나가 주어집니다. (1 ≤ r ≤ n, 1 ≤ c ≤ n)

  • 2 ≤ n ≤ 50
  • 1 ≤ t ≤ 100

출력 형식

t초 후 구슬의 위치가 r행 c열이라 했을 때 r, c 값을 공백을 사이에 두고 출력합니다.

입출력 예제

입력:
  4 4
  1 2 L
출력:
  1 3

✔️ 문제 풀이

  n, t = tuple(map(int, input().split()))
  x, y, d = tuple(input().split()) # x행, y열, 방향
  x, y = int(x) -1, int(y) -1 # (x,y)로 생각하기 위해 -1씩 빼준다

  dxs, dys = [0, 1, -1, 0], [1, 0, 0, -1]
  mapper = {
      'R': 0,
      'D': 1,
      'U': 2,
      'L': 3
  }

  move_dir = mapper[d]

  def in_range(x, y):
      return 0 <= x < n and 0 <= y < n

  for _ in range(t):
      nx, ny = x + dxs[move_dir], y + dys[move_dir]
      if not in_range(nx, ny):
          move_dir = 3 - move_dir
      else:
          x, y = nx, ny

  print(x + 1, y + 1) # x행 y열로 출력하기 위해 +1 해준다.

r행 c열로 입력이 주어지니까 격자로 풀려면 x-1, y-1 해준 뒤 풀고, 다시 x+1, y+1을 해서 행열로 출력한다. dx, dy 테크닉에 방향이 뒤집어지도록 하기 위해 0번과 3번, 1번과 2번이 마주보도록 방향을 설정한다. t초간 진행하면서 주어진 방향으로 1칸씩 움직이되, in_range() 함수를 사용해 구슬이 벽에 부딪히면 방향을 전환하도록 한다.


빙빙 돌며 숫자 적기

문제

n * m크기의 직사각형에 숫자 1부터 순서대로 증가시키며 달팽이 모양으로 채우는 코드를 작성해보세요.

  • 달팽이 모양이란 왼쪽 위 모서리에서 시작해서, 오른쪽, 아래쪽, 왼쪽, 위쪽 순서로 더 이상 채울 곳이 없을 때까지 회전하는 모양을 의미합니다.
  • n : 행(row), m : 열(column)을 의미합니다.
image

입력 형식

n과 m이 공백을 사이에 두고 주어집니다.

  • 1 ≤ n, m ≤ 100

출력 형식

숫자로 채워진 완성된 형태의 n * m 크기의 사각형을 출력합니다.
(숫자끼리는 공백을 사이에 두고 출력합니다.)

입출력 예제

입력:
  4 4
출력:
  1 2 3 4
  12 13 14 5 
  11 16 15 6 
  10 9 8 7

✔️ 문제 풀이

  n, m = tuple(map(int, input().split()))
  x, y = 0, 0
  dir_num = 0

  arr = [
      [0] * m
      for _ in range(n)
  ]

  dxs, dys = [0, 1, 0, -1], [1, 0, -1, 0]

  def in_range(x, y):
      return 0 <= x < n and 0 <= y < m

여기까지는 배운대로 코드를 짰는데 달팽이 모양으로 회전하면서 숫자를 채우는 코드를 어떻게 짜야할 지 감이 안왔다. 코드트리에서 제공한 해답을 참고하여 시뮬레이션 구현 코드를 작성하였다.

먼저 같은 방향으로 진행하다가 방향을 틀어야 하는 경우는 다음과 같다.

```
1) 격자 범위를 벗어난 경우
2) 다음 칸에 숫자가 적혀있는 경우 (이미 방문한 경우)
```


1의 경우는 이전과 같이 in_range(nx, ny) 함수를 사용하여 격자 범위를 벗어났는 지 확인하면 된다.
2의 경우를 확인하기 위해서는 arr[nx][ny] != 0를 사용하여 방문 여부를 확인할 수 있다. 이미 방문한 곳이라면 arr[nx][ny]에 0이 아닌 다른 숫자가 적혀있기 때문이다.

위의 두 조건 중 하나라도 해당한다면 시계방향으로 90도 회전해야 한다
dx, dy 테크닉을 사용하여 시계방향으로 90도 회전하기 위해서는 3 -> 0으로의 방향 회전을 고려해 dir_num = (dir_num + 1) % 4를 사용한다.

위를 고려하여 작성한 코드이다.

  n, m = tuple(map(int, input().split()))
  x, y = 0, 0
  dir_num = 0

  arr = [
      [0] * m
      for _ in range(n)
  ]

  dxs, dys = [0, 1, 0, -1], [1, 0, -1, 0]

  def in_range(x, y):
      return 0 <= x < n and 0 <= y < m

  # 초기값을 설정해준다
  arr[x][y] = 1

  for i in range(2, n * m + 1):
      nx, ny = x + dxs[dir_num], y + dys[dir_num] # 다음 위치 값

      if not in_range(nx, ny) or arr[nx][ny] != 0:
          dir_num = (dir_num + 1) % 4
      
      x, y = x + dxs[dir_num], y + dys[dir_num] # 다음 위치로 이동한 후 
      arr[x][y] = i # 값을 채워넣는다

  for i in range(n):
      for j in range(m):
          print(arr[i][j], end = ' ')
      print()
  • 1부터 n*m까지 1씩 증가하면서 값을 채워넣기 위해 초기값을 arr[0][0] = 1로 설정해두고 for문을 사용하는 게 편하다는 걸 알았음

문제출처: 코드트리의 문제 및 풀이를 정리한 내용입니다.

https://www.codetree.ai/missions/5/problems/small-marble-movement?&utm_source=clipboard&utm_medium=text
https://www.codetree.ai/missions/5/problems/snail-number-square?&utm_source=clipboard&utm_medium=text

© 2021. All rights reserved.

yaejinkong의 블로그