dx, dy 테크닉🥸

학교에서 제공하는 여름방학 코딩 테스트 대비 캠프 with 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석에 수록된 문제 풀이 및 강의 정리 내용입니다.

dx, dy 테크닉이란?

현재 좌표 x, y = (0, 0)이라고 할 때 동쪽으로 이동하면 x = x + 1, y = y + 0, 남쪽으로 이동하면 x = x + 0, y = y - 1, 서쪽으로 이동하면 x = x - 1, y = y + 0, 북쪽으로 이동하면 x = x + 0, y = y + 1으로 좌표가 변하게 된다.

이를 if문으로 표현하게 되면 밑에와 같이 8줄로 표현되는데 이는 비슷한 코드의 반복적인 형태를 지녀 실수를 유발할 수 있다. 이를 해결하기 위해 dx, dy 테크닉이 등장하였다.

순수 if-elif문 사용

x, y = 0, 0 #출발 지점 설정
dir_num = 0 #이동 방향을 나타낸다

if dir_num == 0:
    nx, ny = x + 1, y + 0
elif dir_num == 1:
    nx, ny = x + 0, y - 1
elif dir_num == 2:
    nx, ny = x - 1, y + 0
else:
    nx, ny = x + 0, y + 1

dx, dy 테크닉의 사용 모습

x, y = 0, 0 #출발 지점 설정
dir_num = 0 #이동 방향을 나타낸다

# 방향을 저장하는 순서는 문제에 따라 사용자가 지정
#     0  1   2  3
dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]

#조건에 따라 이동
nx, ny = x + dx[dri_num], y + dy[dir_num]

방향 회전 문제에 dx, dy의 적용

dir_num = 3 #초기 이동 방향
x, y = 1, 5 #초기 위치
dx, dy = [1, 0, -1, 0], [0, -1, 0, 1] #동남서북 순서(시계방향 순)

#==dx, dy 테크닉 사용 안했을 경우==

# 시계방향 90' 회전()
# if dir_num == 0:
#     dir_num = 1
# elif dir_num == 1:
#     dir_num = 2
# elif dir_num == 2:
#     dir_num = 3
# else:
#     dir_num = 0

#==dx, dy 테크닉 사용했을 경우==

# 시계 방향 90' 회전
# 0 -> 1
# 1 -> 2
# 2 -> 3
# 3 -> 0

dir_num = (dir_num + 1) % 4
nx, ny = x + dx[dir_num], y + dy[dir_num]

# 반시계 방향 90' 회전
# 3 -> 2
# 2 -> 1
# 1 -> 0
# 0 -> 3

dir_num = (dir_num -1 + 4) % 4
nx, ny = x + dx[dir_num], y + dy[dir_num]

dx, dy에서 방향 번호를 시계 방향 순서대로 입력했기 때문에 결국 시계 방향으로 90도 회전하는 것은 dir_num을 1 증가시키는 것과 같다.

이때 주의해야 할 점이 존재하는데, 시계 방향으로 회전할 경우 현재 dir_num이 3인 경우 dir_num = dir_num + 1 실행 시 dri_num이 4가 되어 list index out of range 오류가 뜨게 된다.(뱡향은 총 0,1,2,3 4개 까지 존재하기 때문에)

이를 해결하기 위해 dir_num = (dir_num + 1) % 4을 사용한다.

(3+1) % 4 = 0이기 때문에 3->0으로 변경이 잘 이뤄진다.

반시계 방향으로 회전하는 경우에는 시계방향과 반대로 dir_num을 1씩 빼주면 되는데 이 경우에는 바뀌기 전 dir_num이 0인 경우 dir_num = dir_num - 1 수행 시 dir_num이 -1이 되어 위 경우와 동일하게 list index out of range 오류가 뜨게 된다.

이 경우에도 위에 방법과 유사하게 이를 해결하는데 dir_num = (dir_num -1 + 4) % 4를 사용한다.

(0 - 1 + 4) % 4 = 3이기 때문에 0 -> 3으로 변경이 잘 이루어진다.

시계, 반시계가 아니고 특정 지점에서 반대로 돌아 가는 경우라면 이와 같이 코드를 작성

n, t = map(int, input().split())
x, y, dir_c = input().split()

#행,열이 1행 1열부터 시작하므로 -1 씩 해준다.
x = int(x) - 1
y = int(y) - 1

#입력에 따른 방향 지정
dict_dir = {
    "U": 2,
    "D": 1,
    "R": 0,
    "L": 3
}

#dxs, dys를 지정할 때 반대 방향인 걸 계산하기 쉽도록 지정
dir_num = dict_dir[dir_c]
dxs = [0, 1, -1, 0]
dys = [1, 0, 0, -1]

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

for i in range(t):
    nx, ny = x + dxs[dir_num], y + dys[dir_num]

    if in_range(nx, ny):
        x, y = nx, ny
    else:  #반대 방향을 의
        dir_num = 3 - dir_num

    # 초기 풀이(가독성이 떨어짐)
    # if not in_range(nx, ny):
    #     dir_num = 3 - dir_num
    #     continue
    # x, y = nx, ny

#정답을 도출할 때는 빼줬던 1을 다시 더해준다.
x = x + 1
y = y + 1

print(x, y)

• 행, 열이 1행, 1열 부터 시작하기에 입력받은 x,y를 1씩 빼주고 답을 찾은 후 답을 출력할 때 다시 1씩 더해준다. (격자는 행과 열이 0번 인덱스 부터 시작하기 때문에)
• dxs, dys를 지정할 때 동,서 -> 0번,3번 인덱스 / 남,북 -> 1, 2번 인덱스로 두는 이유는 반대 방향을 쉽게 찾기 위해서이다.
• dir_num = 3 - dir_num을 하면 반대방향을 계산할 수 있다.

격자 속 dx, dy

먼저 dx, dy를 이차원 배열(격자)에서 생각해 보면 x를 행, y를 열로 생각해야한다.

다음으로 이동할 위치가 격자에서 벗어나는지를 판단해주는 in_range() 함수를 정의하고 사용해야한다.

상하 좌우에 인접한 1의 개수가 3개 이상인 경우의 수를 구하는 문제를 살펴보자

n = int(input())  #n * n에서의 n
arr = [list(map(int, input().split())) for _ in range(n)] #이차원 배열 입력

#우하좌상
dxs = [0, 1, 0, -1]
dys = [1, 0, -1, 0]

#격자에서 벗어나는지 판단
def in_range(x, y):
    return x >= 0 and x < n and y >= 0 and y < n

result = 0
for x in range(n):
    for y in range(n):ㅑ
        count = 0
        for dx, dy in zip(dxs, dys): 
            nx, ny = x + dx, y + dy
            if in_range(nx, ny) and arr[nx][ny] == 1:
                count += 1
            if count == 3:
                result += 1
                break
print(result)

if in_range(nx, ny) and arr[nx][ny] == 1: 이 코드에서 in_range() 조건이 먼저 수행되어야 한다. if arr[nx][ny] == 1 and in_range(nx, ny):라고 순서를 바꾼다면 arr[nx][ny] == 1에서 index out of range() 오류가 뜨기 때문에 순서를 주의해야 한다.

dx, dy in Python

• python을 사용하여 dx, dy technique을 사용한다면 dx, dy 배열을 dxs, dys라고 선언한 후 여러 개의 collection을 인자로 받아 순서대로 첫번째 원소부터 마지막 원소까지 쌍으로 return해주는 zip 함수를 사용하여 dx, dy를 추출하여 사용한다.

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

for dx, dy in zip(dxs, dys):
    x, y = x + dx, y + dy

• for문 안에 리스트, dictionary 선언 시 크기를 보고 for문 안에 둘지 밖에 둘지 생각해보아야 한다

• map으로 return 후 형변환을 하지 않는다면 len()과 같은 리스트가 제공하는 메소드를 사용할 수 없다. 따라서 파이썬 map사용 시 return 값이 map이므로 tuple이나 list로 감싸주는 것이 좋다.

  • ex) tuple(map(int, arr))

  결론 : unpacking 시 형변환을 하고 진행!!

• 딕셔너리를 사용하여 dir_num과 방향을 나타내는 입력형식을 매핑해준다.

#입력에 따른 방향 지정
dict_dir = {
    "U": 2,
    "D": 1,
    "R": 0,
    "L": 3
}
dir_num = dict_dir[입력값]