백준 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이 움직일때마다 큐에서 값을 빼서 풀었습니다!
Author And Source
이 문제에 관하여(백준 3190번 뱀), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@josajang98/백준-3190번-뱀저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)