Python_수업 (6)

2024.04.12 (금)

 

오늘 할 일

2차원 리스트와 델타 탐색

---

2차원 리스트와 델타 탐색

1. 모듈러 연산

• 나머지로 깎아 버린다. ex. 0 1 2 3 0 1 2 3 …

2. 몫 연산

• 2차원 리스트 순회할 때 사용

matrix = [[3, 7, 9], 
          [4, 2, 6], 
          [8, 1, 5]]
          
for i in range(9):
    print(matrix[i // 3][i % 3])
    
    
#쓸 일 많이 없다 그냥 이중 for 문 돌리자

3. 델타 탐색 기법

• 상하좌우 움직이는 구현
• “delta” (작은 값) → 알고리즘에서는 이차원 리스트의 한 칸

new_r -> nr
new_c -> nc

nr = r + dr
nc = c + dc

[상] -> dr : -1 /. dc : +0
[우] -> dr : +0 /. dc : +1
[하] -> dr : +1 /. dc : +0
[좌] -> dr : +0 /. dc : -1

<코드로 구현> -> 로봇청소기 처럼...
dr = [-1, 1, 0, 0]
dc = [0, 0, 1, -1]
      상  하 우  좌
for i in range(4):
    nr = r + dr[i]
    nc = c + dc[i]

arr = [[1, 2, 3], 
       [4, 5, 6], 
       [7, 8, 9]]
r = c = 1
dr = [1, -1, 0, 0]  # 하 상 좌 우
dc = [0, 0, -1, 1]
for i in range(4):
    nr = r + dr[i]
    nc = c + dc[i]
    print(arr[nr][nc])

• 예외 처리도 해줘야한다.→ 맵 제한 걸기 nr, nc 구하는 건 괜찮은데, M[nr][nc] 이 때 오류가 나온다. → call 하지 말고 continue 해!!

4. 맵 제한 걸기

arr = [[1, 2, 3], 
       [4, 5, 6], 
       [7, 8, 9]]
N = 3
r = c = 2   # 9 위치!! 하, 우 가 되지 않는다!! 에러!!!
dr = [1, -1, 0, 0]  # 하 상 좌 우
dc = [0, 0, -1, 1]
for i in range(4):
    nr = r + dr[i]
    nc = c + dc[i]
    if nr < 0 or nr >= N or nc < 0 or nc >= N:  # 에러 해결!!
        continue
    print(arr[nr][nc])
    
# 또 다른 방식

arr = [[1, 2, 3], 
       [4, 5, 6], 
       [7, 8, 9]]
N = 3
r = c = 2   # 9 위치!! 하, 우 가 되지 않는다!! 에러!!!
dr = [1, -1, 0, 0]  # 하 상 좌 우
dc = [0, 0, -1, 1]
for i in range(4):
    nr = r + dr[i]
    nc = c + dc[i]
    if 0 <= nr < N and 0 <= nc < N:    # 에러 해결!!
        print(arr[nr][nc])

X, Y 축에서의 delta

def solution(command):
    x = y = d = 0  # 초기 좌표와 방향
    dx = [0, 1, 0, -1]  # 상 우 하 좌
    dy = [1, 0, -1, 0]

    for move in command:
        if move == "R":
            d += 1
        elif move == "L":
            d -= 1
        elif move == "G":
            x += dx[d % 4]
            y += dy[d % 4]
        elif move == "B":
            x -= dx[d % 4]
            y -= dy[d % 4]

    return [x, y]

print(solution("GRGLGRG"))  # [2, 2]
print(solution("GRGRGRB"))  # [2, 0]

달팽이 문제

# 1954_달팽이숫자

# 첫 번째 풀이

dr = (0, 1, 0, -1)
dc = (1, 0, -1, 0)

for tc in range(1, int(input()) + 1):
    N = int(input())

    snail = [[0] * N for _ in range(N)]
    r, c, d = 0, 0, 0

		# 1부터 N**2까지 차례로 순회하며 할당합니다.
    for num in range(1, N ** 2 + 1):
				# 해당 좌표에 해당 숫자를 할당합니다.
        snail[r][c] = num

				# 기본적으로 기존 방향을 유지하며 다음 좌표를 설정합니다.
        nr, nc = r + dr[d], c + dc[d]

				# 다음 좌표가 범위를 벗어나는 경우 또는 다음 좌표에 이미 숫자가 할당된 경우 방향을 전환합니다.
        if nr < 0 or nr >= N or nc < 0 or nc >= N or snail[nr][nc] != 0:
						# 아래와 같이 방향 전환 좌표를 설정하면 3 => 0으로의 방향 전환이 가능합니다.
            d = (d + 1) % 4
            nr, nc = r + dr[d], c + dc[d]

				# 위에서 계산한 다음 좌표를 현재 좌표로 최신화한 후 다음 반복으로 넘어갑니다.
        r, c = nr, nc

    print(f'#{tc}')
    for ans in snail:
        print(*ans)

if nr < 0 or nr >= N or nc < 0 or nc >= N or snail[nr][nc] != 0:

'''
이부분 거꾸로 쓰면 안된다!! 즉,
if snail[nr][nc] != 0 or nr < 0 or nr >= N or nc < 0 or nc >= N:
이러면 터진다.

-> 단축평가!! 제대로 써야 'snail[nr][nc] != 0' 까지 왔을 때 앞부분이 맵 보장이 된다는 뜻이다.
'''

# 두 번째 풀이

dr = [0, 1, 0, -1]  #우하좌상
dc = [1, 0, -1, 0]

for tc in range(1, int(input())+1):
    N = int(input())
    snail = [[0 for _ in range(N)] for _ in range(N)]

    d = 0  # 방향
    num = 0  # 달팽이 안에 넣을 숫자
    r = 0  # 행 좌표
    c = -1  # 시작 cell은 0이여야하는데, 아래코드로 시작하면 (0, 1)에서 시작. 따라서 (0,0) 옆 왼쪽의 가상의 칸에서 시작한다

    for i in range(N * 2, 1, -1):  # 방향바꾸기 횟수 2N-1
        for _ in range(i // 2):  # 각 방향에서 움직임 횟수
            num += 1
            r += dr[d % 4]
            c += dc[d % 4]
            snail[r][c] = num
        d += 1  # 방향 바꾸기

    print(f'#{tc}')
    for ans in snail:
        print(*ans)