• 5주차 과제 - 대표 선발(구현 알고리즘(시뮬레이션과 완전 탐색)) 단, turn은 10000 이하이다.

image image image

  • 사용 언어 : python

  • 해결 날짜 : 2021-04-07

  • 느낀점 및 해결 과정 :

    • 이번 과제는 2차원 리스트에 판을 지렁이는 1, 먹이는 -1, 빈 공간은 0의 값을 가지도록 초기화 하였다. 또 R, D, L, U에 맞는 벡터인 dx, dy를 정의하여 각 turn 마다 x와 y에 각각 dx와 dy값을 더해주었다. 여기서 dx, dy의 인덱스는 0부터 3까지로 만약 R이 입력되면 +1, L이 입력되면 -1을 해주었다.(0일 때 -1은 3으로, 3일 때 +1은 0으로 처리)
    • 판의 크기 N, 사과의 개수 K, 방향 전환 횟수 M, 사과의 위치, 방향 전환 정보 direction_change를 각각 입력 받는다.
    • 초기화를 다 하고 난 뒤, 게임이 시작하면 현재 turn을 1씩 증가시키고 x와 y에 각각 현재 방향에 맞는 방향 벡터 값을 더해준다. 그 후 게임이 종료되는 조건인 판 밖으로 나가 게임이 끝나는 경우, 자신의 몸의 부딪혀 게임이 끝나는 경우, turn의 개수가 10000보다 커져 게임이 끝날 경우의 세가지 경우를 검사하여 만약 세 경우 중 하나라도 만족하면 break로 게임을 종료한다. 세 조건 모두 만족하지 않는다면 게임이 지속되고, 방향 전환 정보가 저장된direction_change가 비어 있지 않다면 하나를 꺼내 와서 몇 번째 턴에 방향을 바꾸나(move_count)와 어느쪽으로 방향을 바꾸나(change)를 저장한다. 그 후 방향 전환 turn이 됐다면(move_count == turn), 아까 저장했던 정보를 pop하여 queue에서도 없애주고, 방향을 바꾸어준다(d를 변경) 마지막으로 이동할 때는 먹이가 없는 경우에는 worm.pop()으로 꼬리를 잘라 그 위치의 값을 0으로 만들어주고, 먹이가 있던 없던 이동은 하므로 이동하기 전의 지렁이 위치를 worm에 추가하고 이동한 곳의 지렁이 위치의 값을 1로 만들어준다.

    • 과제를 해결하며 처음에는 단순히 사용자가 M을 얼마나 잘 입력받느냐에 따라 시간 복잡도가 결정될 것이라 생각했는데, turn의 조건이 생기고 turn에 따라 시간 복잡도가 결정될 것이라 예상했다.

    • 시간 복잡도 :

      • 판 초기화 : N2
      • 사과가 있는 인덱스 초기화 : K, 방향 전환 정보 초기화 : M
      • while문 : T(turn의 개수) + N
      • 최악의 경우를 구하는 것이므로 turn이 10000일 때, N이 100일 때, K가 100일 때 이다. M은 아무리 커도 10000보다는 작다. 따라서 시간 복잡도는 O(N2+K+M+T+N) = O(2T) = O(T)일 것이라 예상한다.
    • 코드
    import collections

N = int(input()) # 판의 크기
K = int(input()) # 사과의 개수
M = int(input()) # 방향 전환 횟수

board = [[0] * N for _ in range(N)] # 판 초기화
board[0][0] = 1 # 지렁이의 시작 위치는 1,1
# 판 위에서 지렁이는 1, 먹이는 -1, 빈 공간은 0

turn = 0
x, y = 1, 1 # 처음 시작 위치
worm = [(x, y)] # 지렁이가 있는 위치를 저장(머리부터 꼬리까지)
d = 0 # 방향 ( R:0 D:1 L:2 U:3 )

# R, D, L, U
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

# 사과가 있는 인덱스의 값은 -1로 초기화
for _ in range(0, K):
    i, j = input().split(" ")
    board[int(i)-1][int(j)-1] = -1

# 방향 전환 정보
direction_change = collections.deque()
for _ in range(0, M):
    i, j = input().split(" ")
    direction_change.append((int(i), j))

while True:
    turn += 1
    x += dx[d]
    y += dy[d]

    # 판 밖으로 나가 게임이 끝나는 경우
    if x < 1 or y < 1 or x > 5 or y > 5:
        break
    # 자신의 몸의 부딪혀 게임이 끝나는 경우
    if board[x-1][y-1] == 1:
        break
    # turn의 개수가 10,000보다 커져 게임이 끝날 경우
    if turn >= 10000:
        break

    # 방향 전환 정보 저장(정보가 남아 있을 경우)
    if direction_change:
        move_count, change = direction_change[0]

    # 방향 전환 turn이 됐을 때
    # (pop(0)는 O(n)이므로) deque의 popleft() 사용
    if move_count == turn:
        direction_change.popleft()

        # 방향 바꾸기
        if change == 'R':
            d = d + 1 if d < 3 else 0
        elif change == 'L':
            d = d - 1 if d > 0 else 3

    # 먹이가 없는 경우 꼬리 자르기
    if board[x-1][y-1] == 0:
        tailX, tailY = worm.pop()
        board[tailX-1][tailY-1] = 0

    # 먹이가 있던 없던 전진
    worm.insert(0, (x, y))
    board[x-1][y-1] = 1
print(turn)