191007 백준 알고리즘 문제풀기

|

[3190번] 경사로

  • 난이도: 상
    • 시뮬레이션 문제로, 푸는데 2시간 이상 소요됐다. 시험에 나왔으면 망쳤을 문제다.
      • 문제 풀이 떠올리는데 1시간, 구현하면서 1시간 이상 소요
        • 문제의 조건을 정말 자세히 봐야할것 같다. 모든 조건이라도 세세하게 고려하고 판단해야 한다.
        • 문제를 너무 복잡하게 생각하다보니 자꾸 시간을 낭비하는듯 하다.
    • bfs 등 틀에 갇혀서 생각하기 때문에 더 풀기 어렵게 느껴졌던 것 같다.
      • 좀 더 유연하게 생각할 필요가 있음..
    • 또한, 행 열을 헷갈리게 써놨다. 짜증난다.
      • 열 위치인지 열의 위치인지, 행 위치인지 행의 위치인지 정확하게 조건이 구분되면 좋겟다.
        • 문제의 조건 자체가 좀 모호하게 나열되어있다.
        • 열 위치면 열 내의 위치므로 y좌표가 되는것이고
        • 열의 위치면 행에 존재하는 열의 인덱스므로 x좌표가 된다.
  • 문제
    • https://www.acmicpc.net/problem/3190
    • NxN 크기의 맵이 주어진다.
    • 사과의 개수 K와 좌표가 y, x 좌표 순으로 입력된다.
    • 방향변환 이동횟수 L과 방향변환하는 타이밍, 방향이 입력된다.
    • 전체 맵과 환경을 완성하고, 몇초동안 뱀이 움직일 수 있는지 계산해야 한다.
    • 조건
      • 맵은 몸의 길이를 우선 늘려서 다음 칸에 간다.
        • 아직 이동한것이 아님
      • 만약 다음 칸에 사과가 있으면 몸 길이를 늘린다.(1칸 늘림)
      • 만약 다음 칸에 사과가 없으면 몸 길이를 다시 수축시킨다.(1칸 당김)
      • 입력으로 주어지는 방향변환 이동횟수는 그 시간만큼 이동 후 변경하는것이 아니라 전체 시간 중 해당 타이밍에 변환하는것이다
  • 풀이
    • 전체적으로 조건이 애매해서 애매한 조건 속에서 왓다갓다 하다보니 시간이 많이 낭비되었다.
      • x, y 좌표 정의를 확실하게 하고
      • 정확하게 뱀이 어느 시점에 이동하여 해당 위치가 check 되는지
      • 방향변환이 해당 시점으로부터 그 이후인지, 처음부터 시작된 timing에서 해당 시간인지
      • 위 세 가지 조건이 명확하지 않아 엄청 시간을 날린듯 하다.
    • 문제를 나눠보면
      • 우선, 맵을 완성시킨다.
        • 맵에는 모서리 벽과 사과의 위치가 존재함
        • check 배열에는 벽의 위치만 집어넣는다.
      • 이동해야하는 순서를 moves 큐에 집어넣는다.
      • while문을 돌면서 뱀을 이동시킨다.
        • 다음 위치를 보고, 다음 위치가 접근 가능하다면 다음 위치를 snake큐에 집어넣는다.
          • snake 큐는 snake가 위치하는 좌표값들을 저장한다.
          • 만약 접근 불가능하다면 게임이 끝난것이므로 return으로 빠져나온다.
        • 다음 위치에 사과가 존재한다면
          • snake의 길이는 한 칸 길어진다. 따라서 별도의 연산이 필요 없다.
        • 다음 위치에 사과가 존재하지 않는다면
          • snake의 길이는 늘어나지 않는다. 따라서 가장 처음 들어간 값을 앞에서 뽑아준다.
            • 큐는 FIFO!
        • 만약 방향을 전환할 타이밍이라면
          • 즉, 아직 움직여야 하는 현재 시간이 움직여야 할 시간이라면
          • 방향을 전환한다.
#pragma warning(disable:4996)
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <tuple>
#include <deque>

using namespace std;

int map[102][102]; // 맵 저장용
int check[102][102]; // 뱀 움직임 연산용
queue<pair<int, char>> moves; // 움직임 

int answer = 0;

int dx[] = { 0,1,0,-1 }; // 각각 방향을 상 우 하 좌 를 0, 1, 2, 3으로 매핑
int dy[] = { -1,0,1,0 };

void init(int N)
{ // 맵 테두리 벽 치기
	for (int i = 0; i < N; i++)
	{
		map[0][i] = -1;
		map[N - 1][i] = -1;
		check[0][i] = -1;
		check[N - 1][i] = -1;
	}
	for (int j = 0; j < N; j++)
	{
		map[j][0] = -1;
		map[j][N - 1] = -1;
		check[j][0] = -1;
		check[j][N - 1] = -1;
	}
}
int turn_right(int cd)
{ // 우회전
	if (cd == 0) return 1;
	else if (cd == 1) return 2;
	else if (cd == 2) return 3;
	else return 0;
}
int turn_left(int cd)
{ // 좌회전
	if (cd == 0) return 3;
	else if (cd == 3) return 2;
	else if (cd == 2) return 1;
	else return 0;
}

int turn(int cd, char d)
{ // 회전시키기
	if (d == 'L')
		return turn_left(cd);
	else
		return turn_right(cd);
}

void snake_move(int x, int y, int d, int N)
{ // 뱀 움직이기
	queue<pair<int, int>> snake; // 뱀 몸 좌표 저장용
	check[y][x] = 1; // 최초 위치 초기화
	snake.push(make_pair(x, y)); // snake에 현재 좌표 넣기
	int cd = d; // 현재 방향 초기화

	int time = 0;
	
	while (1)
	{	
		time++; // 시간 증가
		int cx, cy;
		cx = snake.back().first; 현재 위치 초기화
		cy = snake.back().second;
		int nx, ny;
		nx = cx + dx[cd];
		ny = cy + dy[cd];
		if (check[ny][nx] != 0 || (nx <= 0 && N + 1 <= nx && ny <= 0 && N + 1 <= ny))
		{ // 뱀의 머리가 몸에 부딧히거나 벽이면 끝낸다.
			answer = time;
			return;
		}
		check[ny][nx] = 1; // 다음 위치가 접근 가능한경우 접근
		snake.push(make_pair(nx, ny)); // 다음 위치를 큐에 넣는다.

		if (map[ny][nx] == 1)
		{//다음에 사과가 있다면
			map[ny][nx] = 0; // 사과 먹기
		}
		else
		{//사과가 없다면
			int tx, ty;
			tx = snake.front().first;
			ty = snake.front().second; // 뱀 몸이 위치하는데서 맨 꼬리값을 반환받고
			check[ty][tx] = 0; // 꼬리칸 지운다.
			snake.pop(); // 지우기
		}

		if (!moves.empty() && moves.front().first == time)
		{//움직여야 할 경우가 남아있고, 움직일(방향전환) 시간이 되었다면
			cd = turn(cd, moves.front().second); // 방향을 전환한다.
			moves.pop(); // 방향 전환 후 이전 방향값들은 pop.
		}
	}
}

int main()
{
	//
	int N, K;
	scanf("%d", &N);
	scanf("%d", &K);
	
	init(N + 2);
	
	while (K--)
	{
		int x, y;
		scanf("%d %d", &y, &x);
		map[y][x] = 1;
	}
	int L;
	scanf("%d", &L);
	
	while (L--)
	{
		int t;
		char d;
		cin >> t;
		cin >> d;
		moves.push(make_pair(t, d));
	}

	snake_move(1, 1, 1, N);
	printf("%d\n", answer);

	//system("pause");
	return 0;
}