[BOJ] 3190. 뱀

https://www.acmicpc.net/problem/3190

3190번: 뱀

 

 

1. 해결방법

전형적인 시뮬레이션 구현 문제이다.
조건 자체가 있다보니 코드가 조금 길어져서 살짝 헤맸던 코드이다. 그래도 큰 어려움은 없었다.

1. 2차원 배열인 maps에 빈 공간은 0, 사과는 1, 뱀이 있는 곳은 2로 둔다.
2. 방향 정보를 turns 리스트에 정보를 담는다.
3. deque를 이용해서 큐를 만든다. 꼭 deque가 아니고 리스트를 사용하면 됨. 본인은 습관성 deque라서;;;
4. dy, dx 그래프 이동 방향을 설정 (시작은 동쪽부터 이동하니 0번째 인덱스에는 동쪽으로 설정해야한다)
5. 그래프 범위에 벗어나지 않게 탐색하면서 큐에 append 한다. 
6. 만약 사과가 있을 경우, 값을 2로 갱신하고 append하면 되지만, 사과가 없으면 2로 갱신하고 append한 다음 꼬리에 위치한 값을 0으로 갱신시켜줘야 한다.
7. time 카운트를 하면서 turns 리스트에 해당 time에 도달했다면 분기문을 이용해서 방향을 전환해주는 코드를 작성.

 

 

2. 정답코드

import sys
input = sys.stdin.readline
from collections import deque

# input
N = int(input())
K = int(input())
maps = [[0] * (N + 1) for _ in range(N + 1)]
for _ in range(K):
    a, b = map(int, input().split())
    maps[a][b] = 1

turns = []
L = int(input())
for _ in range(L):
    X, C = input().split()
    turns.append((X, C))


# main
dy, dx = [0, 1, 0, -1], [1, 0, -1, 0]
q = deque()
ey, ex = 1, 1
q.append((ey, ex))
direction = 0
time = 0
idx = 0

while True:
    ny, nx = ey + dy[direction], ex + dx[direction]
    if 1 <= ny <= N and 1 <= nx <= N and maps[ny][nx] != 2:
        if maps[ny][nx] == 0:
            maps[ny][nx] = 2
            q.append((ny, nx))
            py, px = q.popleft()
            maps[py][px] = 0
        if maps[ny][nx] == 1:
            maps[ny][nx] = 2
            q.append((ny, nx))
    else:
        time += 1
        break

    ey, ex = ny, nx
    time += 1

    if time == int(turns[idx][0]):
        if turns[idx][1] == 'L':
            direction = (direction - 1) % 4
        else:
            direction = (direction + 1) % 4

        if idx < L - 1:
            idx += 1

print(time)