dx, dy 테크닉
단위 시간마다 추적하고 있는 위치에서 규칙적으로 얼만큼 떨어진 부분을 보고 문제조건에 맞게 코드를 짜는 테크닉이다. 주로 상하좌우로 많이 사용된다.
상하좌우를 조건문으로 나눠서 본다면 현재 위치가 x,y 라면 다음 위치는 x+1, y / x, y-1 / x-1, y / x, y+1 네 가지 좌표를 확인해야한다. 그러면 비슷한 코드를 4번 적어줘야해서 쌩으로 적어준다면 실수할 가능성도 크고 번거롭다.
이때, dx, dy 테크닉을 사용하면 편하다.
x 의 증가량을 dx 라고 하고, y 의 증가량을 dy 라고 할 때
모든 경우의 수에 대해 표를 만들 수 있다. 이러한 표는 배열로 표현할 수 있는데 dx, dy 를 각각 배열로 나타낸다면 이를 합쳐서 방향이란걸 정할 수 있다 .
| 0 | 1 | 2 | 3 | |
|---|---|---|---|---|
| dx | 1 | 0 | -1 | 0 |
| dy | 0 | -1 | 0 | 1 |
예를 들어 (dx[0], dy[0]) 일때는 방향이 x 방향으로 +1 y 는 변함없음 이고, 좌표평면 생각한다면 동쪽이다.
(dx[1], dy[1]) 일 때는 방향이 x 방향으로 0 y 방향으로 -1이고 좌표평면을 생각한다면 남쪽이다. 이런식으로 4개의 방향을 정의할 수 있다.
격자 안에서 단일 객체을 이동
2차원 배열에서 시작점에서 출발해서 인접한 4개의 칸을 본 후 조건에 맞는 걸 찾고 해당 방향으로 이동하거나 그러한 처리를 해주는 문제이다. 이때 조건에 맞는 게 여러개라면 우선순위가 높은 곳으로 이동한다. 우선순위는 문제에 나와있으면 문제대로 없다면 내가 정해준다(ex) 먼저 나온 순서대로)
1. 숫자가 더 큰 인접한 곳으로 이동
https://www.codetree.ai/missions/2/problems/move-to-larger-adjacent-cell/description
내가 짠 코드
n, r, c = list(map(int, input().split()))
arr = [list(map(int, input().split())) for _ in range(n)]
results = []
# 상 하 좌 우
dxs = [0, 0, -1, 1]
dys = [-1,1,0, 0]
def in_range(x, y):
return x>=0 and x<n and y>=0 and y<n
x, y = c-1, r-1
def simulation(x, y):
for dx, dy in zip(dxs, dys):
nx, ny = x + dx, y+dy
if in_range(nx, ny):
if (arr[ny][nx]>arr[y][x]):
results.append(arr[ny][nx])
simulation(nx, ny)
break
return results
print(arr[y][x], end=' ')
results = simulation(x,y)
for elem in results:
print(elem, end=' ')
2. 떨어지는 1차 블록
https://www.codetree.ai/missions/2/problems/falling-horizontal-block/description
입력
4 3 1
0 0 0 0
0 0 0 1
1 0 0 1
1 1 1 1
출력
0 0 0 0
1 1 1 1
1 0 0 1
1 1 1 1
우선 4by4 배열이 주어진다. 그리고 두번째 3이란 숫자는 [가로 3칸 세로 1칸]의 나무블록이 떨어짐을 의미한다. 마지막 1 의 숫자는 떨어지는 위치를 의미한다. (1x3)의 나무블록이 1열부터 3칸까지 떨어진 후 배열을 출력해야한다.
내가 짠 코드
# 1*m 의 블록을 한 행씩 내려야한다.
# 1. 다음 행의 m 개의 열이 비어있는 지 확인
# 2.1 m 개의 행이 다 비어있다면 1*m 블록의 위치를 다음 행으로 내린다.
# 2.2 m 개의 행이 다 비어있지 않다면 종료한다.
n, m, k = list(map(int, input().split()))
k = k-1
grid = [list(map(int, input().split())) for _ in range(n)]
def is_empty(idx, k, m):
for j in range(k,k+m):
if grid[idx][j] == 1:
return False
return True
now_idx = 0
for i in range(n):
if is_empty(i, k, m):
now_idx = i
else:
break
for j in range(k, k + m):
grid[now_idx][j] = 1
for i in range(n):
for j in range(n):
print(grid[i][j], end= ' ' )
print()
격자 안에서 여러 객체를 이동
이번에는 여러개를 한 칸 이동시킨다.
.
1. 숫자가 가장 큰 인접한 곳으로 동시에 이동
- 여러 개를 한 칸 이동시킨다(더 큰게 있다면) 2. 겹치는 객체가 있다면 제거한다. 3. 이동이 모두 불가능하면 종료한다.
https://www.codetree.ai/missions/2/problems/move-to-max-adjacent-cell-simultaneously?&utm_source=clipboard&utm_medium=text
입력 형식
첫 번째 줄에는 격자의 크기를 나타내는 n과 구슬의 개수를 나타내는 m, 그리고 시간을 나타내는 t값이 각각 공백을 사이에 두고 주어집니다.
두 번째 줄 부터는 n개의 줄에 걸쳐 각 행에 해당하는 n개의 숫자가 공백을 사이에 두고 주어집니다.
그 다음 줄 부터는 m개의 줄에 걸쳐 각 구슬의 시작 위치를 나타내는 r, c 값이 각각 공백을 사이에 두고 주어집니다. r, c는 r행 c열에서 시작함을 의미하며, 모든 구슬의 시작 위치는 다르다고 가정해도 좋습니다. (1 ≤ r, c ≤ n)
출력 형식
t초 이후 격자판 이후 남아있는 구슬의 수를 출력합니다.
2 ≤ n ≤ 20
1 ≤ m ≤ n * n
1 ≤ t ≤ 100
예제로 이해해보자.
입력
4 3 1
1 2 2 3
3 5 10 15
3 8 11 2
4 5 4 4
2 2
3 4
4 2
출력
3
위의 예제에 대해 격자의 크기는 4고 구슬의 개수는 3개 시간은 1이다.
그리고 4x4 의 배열이 나온 후 구슬의 위치 3개가 (r행,c열)로 입력된다.
그렇다면, 2행 2열의 구슬1, 3행 4열의 구슬2, 4행2열의 구슬3 에 대해 1초에 상하좌우 방향 순서대로 상하좌우 중에서 가장 큰 값이 적혀있는 방향으로 이동한다. 그걸 t 초 간 반복해야하는데 입력받은 시간은 1 로 한 번만 이동하게 된다.
따라서 구슬1은 10으로 이동하고 구슬2는 15로 이동하고 구슬 3은 11로 이동한다. 충돌하지 않았으므로 남아있는 구슬의 수는 3이다.
2. 숫자의 순차적 이동
https://www.codetree.ai/missions/2/problems/sequential-movement-of-numbers/description
입력 형식
첫 번째 줄에는 격자의 크기를 나타내는 n과 턴의 수를 나타내는 m 값이 공백을 사이에 두고 주어집니다.
두 번째 줄 부터는 n개의 줄에 걸쳐 각 행에 해당하는 n개의 숫자가 공백을 사이에 두고 주어집니다. 1이상 n * n이하의 숫자가 정확히 한 번씩만 나온다고 가정해도 좋습니다.
2 ≤ n ≤ 20
1 ≤ m ≤ 100
출력 형식
m번의 턴을 거친 이후 격자판의 상태를 출력합니다.
n개의 줄에 걸쳐 각 행에 해당하는 n개의 숫자를 공백을 사이에 두고 출력합니다.
입력 예시
4 2
15 13 1 11
4 8 3 5
2 12 16 7
14 6 9 10
출력 예시
13 4 1 9
12 15 7 11
14 2 5 16
6 8 3 10
예제를 살펴보면 4를 입력받았으므로 우선 4x4 의 배열이다. 턴의 수는 2이다. 2번의 턴에 걸쳐 숫자들을 이동시킬 것이다. 숫자 1부터 시작해서 1의 사방 중 가장 큰 애인 13와 swap 한다. 그리고 숫자 2는 14와 swap 하고 이런식으로 nxn(여기서는 16) 까지 swap 해준다.
