백준 3190번 뱀

문제

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

코드

cpp

#include <string>
#include <vector>
#include<algorithm>
#include <iostream>
#include <queue>
using namespace std;

int N, K, L;

bool isRange(int y, int x) {
	if (0 <= y && y < N && 0 <= x && x < N) return true;
	else return false;
}

int main() {
	
	cin >> N >> K;

	vector<vector<int>> map(N, vector<int>(N, 0));
	map[0][0] = 1;
	for (int i = 0; i < K; i++) {
		int y, x;
		cin >> y >> x;
		map[y-1][x-1] = 2;
	}

	cin >> L;
	vector<pair<int, char>> move(L+1);
	for (int i = 0; i < L; i++) {
		cin >> move[i].first;
		cin >> move[i].second;
	}
	move[L] = { 100,'D' };
	int d = 0; //현재 나의 방향
	int dist[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };


	
	int time = 0;
	pair<int, int> head = { 0,0 };
	pair<int, int> tail = { 0,0 };

	queue<int> q;
	for (auto i : move) {
		while(time< i.first) {
			head.first += dist[d][0];
			head.second += dist[d][1];
			int headY = head.first;
			int headX = head.second;
			q.push(d);
			time++;
			if (!isRange(headY, headX)|| map[headY][headX] == 1) { //범위를 벋어나거나 자기 자신과 부딪히면 종료
				cout <<time;				
				exit(0);
			}			
			
			if (map[headY][headX] == 0) { //빈칸이라면 한칸 움직이고 tail의 인덱스를 변경	
				map[headY][headX] = 1;
				map[tail.first][tail.second] = 0;
				
				tail.first += dist[q.front()][0];
				tail.second += dist[q.front()][1];
				q.pop();
			}
			else if(map[headY][headX] == 2) map[headY][headX] = 1;
			/*for (auto i : map) {
				for (int j : i)
					cout << j << " ";
				cout << endl;
			}
			cout << time<<endl;*/
			
		}
		
		if (i.second == 'D') d++;
		else d--;

		if (d >= 4) d -= 4;
		if (d < 0)d += 4;
	}
	
}

python

import sys

N = int(sys.stdin.readline())
K = int(sys.stdin.readline())
maps = [[0 for _ in range(N)] for _ in range(N)]

for k in range(K):  # mark apple
    r, c = map(int, sys.stdin.readline().split())
    maps[r-1][c-1] = 2

L = int(sys.stdin.readline())
change = dict()
for l in range(L):
    t, d = sys.stdin.readline().split()
    change[int(t)] = d

maps[0][0] = 1
# R,D,L,U
dm = [(0, 1), (1, 0), (0, -1), (-1, 0)]

time = 0
x, y = 0, 0
move = 0
now = [(0, 0)]
while True:
    time += 1
    dy, dx = dm[move]
    nx, ny = x+dx, y+dy
    # on board
    if 0 <= nx < N and 0 <= ny < N:
        # find apple
        if maps[ny][nx] == 2:
            now.append((nx, ny))
            maps[ny][nx] = 1
        # blank
        elif maps[ny][nx] == 0:
            maps[ny][nx] = 1
            now.append((nx, ny))
            rx, ry = now[0]
            del now[0]
            maps[ry][rx] = 0
        # bump self
        elif maps[ny][nx] == 1:
            break
        x, y = nx, ny
        # time of change direction
        if time in change:
            if change[time] == 'L':
                move += -1
                if move >= 4:
                    move -= 4
                elif move < 0:
                    move += 4
            elif change[time] == 'D':
                move += 1
                if move >= 4:
                    move -= 4
                elif move < 0:
                    move += 4
    # out of board
    else:
        break
print(time)

풀이

일단 int 2차원 배열로 맵을 만들고 0,0에 뱀을 나타내는 1을 저장했습니다

사과의 위치값을 입력받아서 맵에 저장시켜두고 뱀의 현재 head 좌표값과 tail 좌표값을 변수로 만들어서 관리 해주었습니다.
head와 tail 인덱스를 관리할때 주의 하실게 현재 head의 진행방향과 tail의 진행방향이 다를 수 있기 때문에 큐를 사용하여 head가 움직일때마다 큐에 방향값을 넣어주고 tail이 움직일때마다 큐에서 값을 빼서 풀었습니다!