학교에서 진행하는 여름방학 코딩테스트 대비 캠프 with CodeTree 의 강의와 문제풀이를 정리한 내용입니다.

dx dy technique이란?

숫자 0이 주어지면 동쪽으로, 
숫자 1이 주어지면 남쪽으로,
숫자 2가 주어지면 서쪽으로, 
숫자 3이 주어지면 북쪽으로 이동하려 합니다.

다음과 같은 문제가 주어진다면 x, y의 좌표를 이동시키며 비슷한 형태의 코드를 반복적으로 사용하게 되어 실수를 유발할 수 있기 때문에 이를 해결하기 위해 dx dy technique을 사용한다.

dir_num = 2 # 시작 방향
x, y = 1, 5 # 시작 좌표
dx, dy = [1, 0, -1, 0], [0, -1, 0, 1]

nx, ny = x + dx[dir_num], y + dy[dir_num] # 이동할 좌표

다음과 같이 각 방향에 맞는 x 좌표의 차를 dx에 y 좌표의 차를 dy에 적어줌으로써 깔끔한 코드 작성이 가능해진다.

---

방향 회전을 위한 dx, dy 정의 방법

(1, 5) 위치에서 시작하며 현재 북쪽을 바라보고 있습니다. 

방향을 시계방향으로 90' 회전한 후, 
앞으로 한 칸 이동한 이후의 위치를 구해보세요.

다음과 같은 문제가 주어졌을 때, 위에서 했던 방법으로 dir_num을 정의하게 된다면 문제가 복잡해지게 된다.

다음과 같이 시계 방향 순서대로 정의를 하게 된다면 dy, dy에서 방향 번호를 시계방향 순서대로 적어 넣었다 보니, 결국 시계방향으로 90' 회전하는 것은 dir_num을 1 증가시키는 것만으로도 가능하다는 것을 알 수 있다.

하지만, dir_num이 3인 경우에는 다시 0이 되어야 하므로 현재 방향이 dir_num이었다면 90' 회전한 이후의 방향은 (dir_num + 1) % 4임을 알 수 있다.

dir_num = 3 # 시작 방향
x, y = 1, 5 # 시작 좌표
dx, dy = [1, 0, -1, 0], [0, -1, 0, 1] # 시계방향 순서

dir_num = (dir_num + 1) % 4 # 회전할 방향

nx, ny = x + dx[dir_num], y + dy[dir_num] # 다음 위치

반시계 방향에 대한 회전은, 현재 dir_num에서 1을 빼주면 되는데 상황에 따라 음수가 되는 경우가 있기 때문에 항상 양수를 만들어 주는 것이 중요하다.

dir_num = (dir_num - 1 + 4) % 4

---

격자에서의 dy, dy

격자가 주어진 경우 격자를 2차원 배열로 표현하여 문제를 해결할 수 있다. 격자에서 역시 dx, dy 테크닉을 이용하면 인접한 상하좌우의 위치를 쉽게 구할 수 있습니다.
다만, 여기서 유의해야할 점은 격자에서의 x, y를 수학에서의 x, y가 아닌 행, 열로 생각해야 한다는 것이다.
(x, y)의 의미를 x행 y열로 생각하면, 다음과 같이 dx, dy를 정의할 수 있다.

여기서 다음과 같이 zip 함수를 사용하여 dxs, dys로 작성하게 되면 가독성이 좋게 코드를 작성할 수 있다.

x, y = 2, 1
dxs, dys = [0, 1, 0, -1], [1, 0, -1, 0]

cnt = 0
for dx, dy in zip(dxs, dys):
    nx, ny = x + dx, y + dy
    if a[nx][ny] == 1:
        cnt += 1

하지만, 이렇게만 코드를 작성하게 되면 index가 범위를 벗어났을 경우 Runtime Error가 발생하게 된다.
이 문제를 극복하기 위해 인접한 위치가 격자 안에 들어오는지를 판단하는 in_range(x, y) 함수를 작성해준다.

# (x, y)가 격자 안에 들어오는 경우에만 True, 그렇지 않다면 False를 반환하는 함수이다.
def in_range(x, y):
	return 0 <= x and x < n and 0 <= y and y < n

✏️ 연습문제 : 1이 3개 이상 있는 위치

숫자 0과 1로만 이루어진 n * n 크기의 격자 상태가 주어집니다. 각 칸 중 상하좌우로 인접한 칸 중 숫자 1이 적혀 있는 칸의 수가 3개 이상인 곳의 개수를 세는 프로그램을 작성해보세요. 단, 인접한 곳이 격자를 벗어나는 경우에는 숫자 1이 적혀있지 않은 것으로 생각합니다.

💻 CODE

n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]

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

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

total_cnt = 0
for i in range(n):
    for j in range(n):
        cnt = 0
        for dx, dy in zip(dxs, dys):
            nx, ny = j + dx, i + dy
            if in_range(nx, ny) and arr[nx][ny] == 1:
                cnt += 1
        
        if cnt >= 3:
            total_cnt += 1

print(total_cnt)

여기서 주의할 부분은 if in_range(nx, ny) and arr[nx][ny] == 1: 이다.
만약 if a[nx][ny] == 1 and in_range(nx, ny) 라고 적는다면 nx, ny의 값이 범위를 넘어간다면 IndexError를 유발하게 된다.
따라서 in_range와 같이 범위를 확인하는 조건의 경우에는 항상 if문 가장 앞에 작성하는 것이 중요하다.

---

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

n * n 크기의 격자 위 (x, y) 위치에서 공이 상하좌우 중 한 방향으로 이동중입니다.
이동 도중 격자 끝에 다다르면, 방향을 반대로 바꿔 다시 움직입니다.
1초에 한 칸씩 움직인다 했을 때, 10초 뒤 공의 위치는 어떻게 되나요?

다음과 같은 문제 또한 방향에 따라 움직이는 문제이므로 dx, dy 테크닉을 사용할 수 있다.
단, 격자 끝에 도착하면 방향을 반대로 뒤집어 줘야 하기 때문에 방향 번호를 잘 정의해주는 것이 중요하다.

0번과 3번이 반대 방향이 되도록하고, 1번과 2번이 반대 방향이 되도록 설정했기 때문에 방향을 뒤집는 작업은 3에서 현재 방향 번호를 빼주면 된다.

n = 5
x, y = 1, 2
dir_num = 2

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

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

while keep_moving():
    nx, ny = x + dxs[dir_num], y + dys[dir_num]
    if not in_range(nx, ny):  
        dir_num = 3 - dir_num # change direction

    x, y = x + dxs[dir_num], y + dys[dir_num]

다음과 같이 코드를 작성해볼 수 있는데, 만약 움직여야 할 방향이 'R', 'D', 'U', 'L'과 같이 문자로 주어진 경우라면 dict를 이용하여 방향과 방향 번호를 key-value 형태로 저장하여 문제를 해결할 수 있다.

✏️ 연습문제 : 작은 구슬의 이동

구슬의 처음 위치와 초기 방향이 주어졌을 때, t초가 지난 이후에 해당 구슬의 위치를 구하는 프로그램을 작성해보세요.

💻 CODE

n, t = map(int, input().split())
r, c, d = input().split()

dxs, dys = [0, 1, -1, 0], [1, 0, 0, -1]
mapper = {
    'R': 0,
    'D': 1,
    'U': 2,
    'L': 3
}
x, y, move_dir = int(r) - 1, int(c) - 1, mapper[d]

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

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

print(x + 1, y + 1)