[알고리즘 코딩캠프 3일차] 2차원리스트 - 회전, 델타 탐색

제가 재학 중인 대학교에서 열린 `파이썬 알고리즘 코딩캠프(25.02.03 ~ 25.02.14)` 수업을 듣고 정리한 글입니다.

목차 :

• 2차원 리스트 
  • 2차원 리스트의 회전
  • 2차원 리스트의 델타 탐색

---

2차원 리스트의 회전

# 1. 반복문을 이용한 시계방향 90도 회전

matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
'''
[
    [7, 4, 1],
    [8, 5, 2],
    [9, 6, 3]
]
'''
n = 3

# rotated_matrix = [[0] * n for _ in range(n)]
# for i in range(n):
#     for j in range(n-1, -1, -1):
#         rotated_matrix[i][2-j] = matrix[j][i]
# print(rotated_matrix)

rotated_matrix = [[0] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        rotated_matrix[i][j] = matrix[2-j][i]
print(rotated_matrix)
# 이렇게 rotated_matrix의 index를 그대로 두고, 나머질 수정하는 게 나음.

rotated_matrix = [[matrix[i][j] for i in range(n-1, -1, -1)] for j in range(n)]
print(rotated_matrix)
# 리스트 컴프리헨션은 이렇게 가능.
# 사실상 위에꺼랑 동일 원리라는 걸 이해하고, 둘 다 할 줄 알아야 함.
print('===================')

# 2. zip을 이용한 시계 방향 90도 회전

matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
'''
[
    [7, 4, 1],
    [8, 5, 2],
    [9, 6, 3]
]
'''

# zip() 기본 설명

print(list(zip([1,2,3], [4,5,6], [7,8,9])))
# [(1, 4, 7), (2, 5, 8), (3, 6, 9)]
# zip() : 인자로 들어온 놈들을 같은 index끼리 튜플로 묶어서,
# 그 튜플들을 원소로 가지는 zip 객체를 반환해줌.

print(list(zip([1,2,3], [4,5])))
# [(1, 4), (2, 5)]
# 길이가 짧은 것에 튜플 개수를 맞춤.

print(list(zip(matrix)))
# [([1, 2, 3],), ([4, 5, 6],), ([7, 8, 9],)]
# 얘는 행렬을 통째로 넣는 거임!
# 우리는 언패킹을 해서, 각각의 리스트를 인자로 넣어야 함.


# 90도 회전 with zip()

print(list(zip(*matrix[::-1])))
# [(1, 4, 7), (2, 5, 8), (3, 6, 9)]
# reversed, reverse, slicing 중 일반적으로 slicing이 가장 빠름!!

# 근데, zip을 쓰면 열끼리 튜플로 묶어주잖아...
# 우리 튜플 리스트 말고, 2차원 리스트로 가지고 싶으면?
zipped_matrix = list(map(list, zip(*matrix[::-1])))
print(zipped_matrix)
# [[7, 4, 1], [8, 5, 2], [9, 6, 3]]


# 강사) 아래쪽의 파이써닉한 코드는, 코테 시간단축을 위한 거지, 
# 위쪽의 기본 코드들부터 마스터한 후 파이써닉한 스킬들을 쓰자!

---

2차원 리스트의 델타 탐색

# 델타 탐색
# : 2차원 리스트의 어떤 위치에서 인접한 곳에 위치한 
#   다른 지점을 조회하거나 이동하는 탐색

# 깊이 우선 탐색과 너비 우선 탐색에서 가장 자주 사용되는 방식.
# 이걸 모르면 향후 4, 5일 정도 문제를 못 품.

# 델타 : (세모표시)x <- x의 변화량. 변량을 의미. 이 변량을 가지고 탐색을 하겠다는 의미.
# 상하좌우 탐색을 할 때, 델타x랑 델타y를 생각해보자는 거임.
'''
A = (1, 1) 일 때,
위 = (0, 1) -> 델타x = -1, 델타y = 0
아래 = (2, 1) -> 델타x = 1, 델타y = 0
좌 = (1, 0) -> 델타x = 0, 델타y = -1
우 = (1, 2) -> 델타x = 0, 델타y = 1
'''

matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

n = len(matrix)
m = len(matrix[0])


# 델타 탐색의 4단계
# 1. 기준점 잡기
# 2. 상하좌우 델타값 정의
# 3. 이동하기
# 4. 범위 확인

# 1. 기준점 잡기
x, y = 1, 1

# 2. 상하좌우 델타값 정의
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 굳이 따지면 (dx, ey) = [상(-1, 0), 하(1, 0), 좌(0, -1), 우(0, 1)]

# 3. 이동하기
# 위로 이동함.
nx = x + dx[0]
ny = y + dy[0]

# 우로 이동함
nx = x + dx[3]
ny = y + dy[3]

# 4. 범위 확인
if 0 <= nx < n and 0 <= ny < m: # 정상 범위면:
    x, y = nx, ny # 그때서야 실제로 이동. 내 기준점을 nx, ny로 바꿔줌.
    # 사실상, 일단 먼저 가보고, 정상 범위인지 확인 후
    # 맞으면 적용, 아니면 그냥 없던 일로.
    # 나중에는 행렬을 나가는 거 말고도, '벽이 있다' 와 같은 것도 나옴.


# 5. 4방향을 모두 차례로 탐색
x, y = 1, 1 # 1. 기준점 잡기
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1] # 2. 상하좌우 델타값 정의
# 3. 이동하기
for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]
    if 0 <= nx < n and 0 <= ny < m: # 4. 범위 확인
        print(matrix[nx][ny]) # 상 하 좌 우 원소 순서대로 출력

print('=============')
# 6. 8방향?
x, y = 1, 1 # 1. 기준점 잡기
# 2. 상 하 좌 우 좌상 좌하 우하 우상 델타값 정의
dx, dy = [-1, 1, 0, 0, -1, 1, 1, -1], [0, 0, -1, 1, -1, -1, 1, 1]
# 3. 이동하기
for i in range(8):
    nx = x + dx[i]
    ny = y + dy[i]
    if 0 <= nx < n and 0 <= ny < m: # 4. 범위 확인
        print(matrix[nx][ny]) # 상 하 좌 우 좌상 좌하 우하 우상 원소 순서대로 출력

# 저 델타들 순서는 내가 문제 상황에 맞게 바꾸면 됨. 뭐 시계 방향으로 돌라든지, 대각선 먼저 가라든지

 

---

과제 및 풀이 정리

<이차원리스트의 회전>

https://cuffyluv.tistory.com/141

<일반 이차원리스트 - 구현력 중점>

- 색종이

- 하얀 칸

- 스도쿠 채점

<이차원리스트의 델타 탐색>
- 이차원 배열의 델타 탐색1

- 공원

- 이차원 배열의 델타 탐색2

- 로봇 여행 게임1

- 로봇 여행 게임2

- 달팽이 순회

- 공원 산책

- 거리두기 확인하기

- 로봇 청소기

- 드래곤 커브