[백준(Baekjoon)][자바(java)] [삼성 SW 역량 테스트 기출 문제] 3190 : 뱀

 

www.acmicpc.net/problem/3190

3190번: 뱀

 

문제 풀이

import java.io.*;
import java.util.*;

public class Main {
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) );
		int n = Integer.parseInt( br.readLine() ), k = Integer.parseInt( br.readLine() ), i;
		boolean a[][] = new boolean[n][n];  // apple array
		StringTokenizer st;
		for( i = 0; i < k; i++ ) {
			st = new StringTokenizer( br.readLine() );
			a[Integer.parseInt(st.nextToken())-1][Integer.parseInt(st.nextToken())-1] = true;
		}
		int l = Integer.parseInt( br.readLine() ), t[][] = new int[l][2];  // turn array
		for( i = 0; i < l; i++ ) {
			st = new StringTokenizer( br.readLine() );
			t[i][0] = Integer.parseInt(st.nextToken());
			t[i][1] = st.nextToken().equals("L") ? -1 : 1;
		}
		br.close();

		int x = 0, y = 0, d = 0, s = 0; i = 0;  // snake head x/y, direction, second, index
		int dx[] = { 0, 1, 0, -1 }, dy[] = { 1, 0, -1, 0 }; String c;  // coordinate
		Queue<String> q = new LinkedList<>();
		q.add( x + " " + y );
		while( true ) {
			s++;
			x += dx[d];
			y += dy[d];
			if( x < 0 || x >= n || y < 0 || y >= n )
				break;
			c = x + " " + y;
			if( q.contains( c ) )
				break;
			q.add( c );
			if( a[x][y] ) 
				a[x][y] = false;
			else 
				q.remove();
			if( i < l && s == t[i][0] ) {
				d += t[i++][1];
				if( d < 0 ) d = 3;
				if( d > 3 ) d = 0;
			}
		}
		
		System.out.println( s );
	}
}

*  n * n 크기의 보드에서, 좌표 ( x, y )의 범위는 0 <= x < n, 0 <= y < n 이다
 ( 사과의 위치 좌표 입력받을 때 1씩 뺌 )

*  방향 변환 정보 배열( t[][] )에서 문자 C( t[i][1] )가 왼쪽('L')이면 -1, 오른쪽('D')이면 1로 취급

*  방향성에 대한 배열( dx[], dy[] )은 동, 남, 서, 북 순서로 함
 ( 반시계방향( -1 ) / 시계방향( 1 ) ) ( 시작과 끝이 연결된 원형 배열처럼 사용 )

*  뱀이 위치한 좌표들은 Queue<String> q에 담음 ( "x y" 형식의 문자열( String c ) 형태로 )

*  초기 상태
-  초 : 0초
-  뱀의 머리 좌표 : ( 0, 0 )
-  뱀의 길이 : 1

*  매 초 마다 ( 1초 간 )
-  뱀의 머리 좌표 ( x, y )를 현재 방향( d : direction )으로 이동 ( x += dx[d]; y += dy[d]; ) ( x, y가 보드의 범위를 넘어가면 끝남 )
-  뱀의 길이를 늘림 => 머리를 ( x, y )에 위치시킴 ( q.add( x + " " + y ); ) ( 뱀의 머리가 몸통과 겹치면 끝남 )
-  ( x, y )에 사과가 있으면 ( a[x][y] == true ) 사과를 먹어서 없앰 ( a[x][y] = false )
-  ( x, y )에 사과가 없으면 ( a[x][y] == true ) 뱀의 꼬리를 줄임 ( q.remove() ) ( 크기는 그대로 )
-  뱀의 방향 정보 배열( t[][] )의 i 번째 초( t[i][0] )가 현재 초( s : second )인 경우 회전 정보( t[i][1] )에 따라 방향 전환

*  s 출력

 

[ 예제 ]  --  초, 뱀의 위치 좌표들, 보드판( ☆ : 사과, ● : 뱀 머리, ■ : 뱀 몸통 )