BOJ 백준 3190 뱀

 

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

 

[ 문제 요약 ]

• 뱀이 사과를 먹으면 길이가 늘어나며 벽이나 자기 자신의 몸과 부딪히면 게임이 끝납니다.
• 게임은 N*N 보드 위에서 진행되고, 몇몇 칸에는 사과가 있습니다.
• 벽은 보드의 상하좌우 끝에 있습니다.
• 게임 시작 시 뱀은 1,1칸에 있고 길이는 1입니다.
• 뱀은 처음에 오른쪽을 향하며 매초 다음 규칙을 따라 이동합니다.

1. 먼저 뱀은 몸길이를 늘려 머리를 다음 칸에 위치시킴
2. 만약 벽이나 자기 자신의 몸과 부딪히면 게임이 끝남
3. 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
4. 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여 꼬리가 위치한 칸을 비움, 즉, 몸길이는 변하지 않음

사과의 위치와 뱀의 이동경로가 주어질 때 몇 초에 게임이 끝나는지 출력합니다.

 

[ 테스트 케이스 설명 ]

6 // 보드 게임의 크기(2<=100)
3 // 사과의 개수(0<=100)
3 4 // K개 줄에 사과의 위치가 주어짐(행Y, 열X)
2 5
5 3
3 // 뱀의 방향 변환 횟수 L(1<=100)
3 D // 게임 시작 시간으로 부터 X(0<=10,000)초 후 왼쪽 혹은 오른쪽으로 90도 회전을 의미(L은 왼쪽 D는 오른쪽)
15 L
17 D
게임이 끝나는 초 출력 : 9

 

[ 알고리즘 분류 ]

• 구현
• 자료 구조
• 시뮬레이션
• 덱
• 큐

 

[ 문제 해설 ]

 

뱀이 이동하는 데 사과를 먹기 전까지 머리 이동 → 꼬리 이동으로 반복하고, 사과를 먹으면 머리만 이동 합니다. 그리고 벽에 닿거나, 자기 자신의 몸에 닿으면 그때의 시간을 출력합니다.

 

여기서 닿는 시간은, 바로 앞이 벽이거나 자기 자신일 때가 아니라, 실제로 겹치게 되는 시간을 출력하면 됩니다. 맞닿아있으나 아직 겹치지 않았다면 끝난 것이 아닙니다.

 

주어지는 방향 전환의 시간은 0초부터 가능하기 때문에 알고리즘 시작 시 방향 전환을 먼저 탐색하고 시작합니다.

 

그리고 초마다 방향 전환을 쉽게 하기 위해 시간에 따른 방향 전환을 담을 일차원 배열을 미리 선언하여 시간만 대입하면 어느 방향인지 바로 알 수 있도록 하는 것이 구현하기 쉽습니다.

 

ex) char dirInfo[];// idx : 몇 초인지 / value : 방향이 뭔지

 

그리고 꼬리 칸을 줄일 때, 다음 꼬리가 무엇인지 알기 위해 뱀의 이동 경로마다 마킹을 해놓아야 합니다. 뱀이 이동할 때마다 이동 경로에 1씩 증가하는 숫자를 놓는다면 다음 꼬리 칸을 찾기 쉽습니다.

 

[알고리즘 흐름]

1. 해당 초에 맞는 방향 전환
2. 1초 증가
3. 해당 방향으로 머리 이동 및 이동 경로에 숫자 마킹 + 유효한지 체크 + 사과 유무에 따라 꼬리 줄이기

위와 같은 흐름으로 작성하기 위해 do while 문을 사용했습니다.

 

[ 정답 코드 ]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
class Main{
	
	static final int APPLE = -1;
	static final int dxy[][] = {{0,1},{1,0},{0,-1},{-1,0}};
	static int fy, fx;// 머리의 위치
	static int ly, lx;// 꼬리의 위치
	static int nowDir;// 현재의 방향
	static int flag;// 뱀이 이동한 방향에 넣을 증감 숫자
	static int time;// 현재 시간
	static int N;// 맵의 크기
	static int map[][];
	static char dirInfo[];// idx : 몇초인지 / value : 방향이 뭔지
	
	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());// 보드게임크기 2<=100
		map = new int[N+2][N+2];
		dirInfo = new char[10_001];

		map[1][1] = ly = lx = flag = fy = fx = 1;// 모두다 1세팅
		
		int appleCnt = Integer.parseInt(br.readLine());// 사과 개수 0<=100
		while(appleCnt-->0)
		{
			st = new StringTokenizer(br.readLine());
			int y = Integer.parseInt(st.nextToken());
			int x = Integer.parseInt(st.nextToken());
			map[y][x] = APPLE; // 사과는 -1
		}
		
		int dirCnt = Integer.parseInt(br.readLine());// 뱀의 방향 전환 횟수(1<=100)
		while(dirCnt-->0)
		{
			st = new StringTokenizer(br.readLine());
			dirInfo[Integer.parseInt(st.nextToken())] = st.nextToken().charAt(0);
		}
		
		do {
			dirChange();// 해당 초에 방향 전환(0초부터 시작)
			
			++time;// 1초 증가
		}while(moveDir());// 해당 방향으로 한칸 이동 및 유효한지 체크

		System.out.print(time);
	}
	static boolean moveDir() {
		fy += dxy[nowDir][0];// 한칸 이동
		fx += dxy[nowDir][1];// 한칸 이동
		
		if(fy == 0 || fx == 0 || N < fy || N < fx || map[fy][fx] > 0)
			return false;
		
		boolean isApple = map[fy][fx] < 0;// 이동 위치가 사과인지 체크
		
		map[fy][fx] = ++flag;// 이동 위치에 마킹
		
		if(isApple) // 사과면 연산 종료
			return true;
		
		int target = map[ly][lx] + 1;// 다음 꼬리번호
		map[ly][lx] = 0;// 꼬리쪽을 한칸 줄인다.
		
		for(int xy[] : dxy) // 다음 꼬리 위치 확인
		{
			int ny = ly + xy[0];
			int nx = lx + xy[1];
			if(map[ny][nx] == target)// 다음꼬리 위치 찾으면 마킹
			{
				ly = ny;
				lx = nx;
				break;
			}
		}
		
		return true;
	}
	static void dirChange() {
		if(dirInfo[time] == 'L')
			nowDir--;
		else if(dirInfo[time] == 'D')
			nowDir++;
		
		if(nowDir < 0)
			nowDir = 3;
		if(nowDir == 4)
			nowDir = 0;
	}
}

 

 

[ 여러 반례들 ]

6
3
2 1
2 2
1 2
5
2 D
3 D
4 D
5 D
6 D
답 : 12
2
0
1
3 D
답 : 2
5
0
5
4 D
8 D
12 D
15 D
20 L
답 : 20
8
3
5 4
5 8
2 5
6
7 D
11 D
15 D
18 D
19 D
20 D
답 : 21
8
5
6 1
7 3
3 5
5 7
5 6
12
2 D
8 D
10 D
12 D
18 L
20 L
22 L
24 L
25 L
28 L
32 D
33 L
답 : 27