백준 알고리즘 10875 : 뱀 (시간초과)

일단 뱀을 정의 해보자

	public class Bam
	{
		public int x, y, moveCount, angle;

		public List<SnakeSegment> body = new List<SnakeSegment>();

		public Bam(int zeroPoint)
		{
			angle = 90;
			x = y = zeroPoint;
			moveCount = 0;
		}

		public void Move()
		{
			SnakeSegment segmet = new SnakeSegment(x, y);
			body.Add(segmet);

			switch(angle)
			{
				case 0: y += 1; break;
				case 90: x += 1; break;
				case 180: y -= 1; break;
				case 270: x -= 1; break;
			}
			moveCount++;
		}
	}

뱀은 자기 자신의 위치(x,y)와 움직인 횟수(moveCount), 회전각(angle)과 몸통인(body)를 가지고 있다.

문제에서 뱀은 처음에 격자판의 중앙에 있고 머리의 방향은 항상 오른쪽이라고 작성되어 있어 생성자에서 이 부분을 셋팅해주었다.

뱀은 스스로 이동할 수 있으며, 이동 할 때 마다 이동한곳 만큼 몸통이 증가한다.

 

Switch문을 어떻게 간단하게 표현할까 고민하면서 삽질을 많이 했다... 문제를 성고하고 나서 다른 사람들은 어떻게 했는지 찾아봐야겠다. 10.13 기준

 

뱀의 몸통

	public class SnakeSegment
	{
		public int X, Y;

		public SnakeSegment(int x, int y)
		{
			X = x;
			Y = y;
		}
	}

처음엔 Bam 클래스에 List<Tuple<int,int>> 변수를 선언해 몸통을 표현했는데 튜플을 활용하기 좀 번거로워서 좌표값만 가지고 있는 몸통 클래스를 만들었다. 

 

입출력을 하는 메인 함수

		static int size, rotation, plate, rotateNum =0;
		static List<char[]> rotationValue = new List<char[]>();
        
		public static void Main()
		{

			size = int.Parse(Console.ReadLine());
			rotation = int.Parse(Console.ReadLine());

			for (int i = 0; i < rotation; i++)
			{
				char[] input = Console.ReadLine().ToCharArray();
				
				rotationValue.Add(input);
			}

			plate = 2 * size;

			Bam bam = new Bam(size);

			while(!IsDead(bam, plate))
			{
				Rotate(bam);
				bam.Move();
				rotateNum++;
			}

			Console.WriteLine(bam.moveCount);
		}

입력 첫 줄에는 L, 두 번째 줄엔 몇번 회전할지 나타내는 정수로 이 값만큼 추가로 입력을 더 받아야 해 for문을 돌려 딕셔너리에 저장한다.

격자판인 plate는 문제에서 2L + 1로 주어져 2차원 배열로 만들어보았지만 계산만 복잡해져 2 * L로 계산 ( 0도 포함하기에 +1은 하지 않았다)

 

뱀 객체를 생성 매개변수인 zeroPoint는 L을 넣어준다( 격자판의 계산식은 2L + 1로 항상 홀수다, 이 격자판의 중앙은 L,L이다 내 계산식에서는 0도 포함하기 때문) 

 

뱀이 죽을 때 까지 while문을 돌며 이동과 회전을 반복후 죽은 뒤 이동횟수를 출력한다. 

 

뱀이 죽었는지 판별

 

public static bool IsDead(Bam bam, int plates)
{
    if (bam.x < 0 || bam.y < 0) return true;
    else if (Math.Abs(bam.x) > plates || Math.Abs(bam.y) > plates) return true;

    foreach(SnakeSegment segment in bam.body)
    {
        if (segment.X == bam.x && segment.Y == bam.y) return true;
    }

    return false;
}

죽었을시 true를 반환하고 살아있다면 false를 반환하는 함수다. 

뱀의 머리가 격자판을 나가면 죽는다. 따라서 뱀의 좌표가 0보다 작을 수 없고, 격자판보다 클 수도 없다. 

 

뱀이 자기 자신의 몸에 닿으면 죽기에 body를 순회하며 현재 위치가 몸과 일치하는지 순회하며 확인한다.

 

뱀 회전

public static void Rotate(Bam bam)
{
    if (rotationValue == null) return;

    int rotateTime = (int)Char.GetNumericValue( rotationValue[0][0]);

    if (rotateTime.Equals(rotateNum))
    {
        if (rotationValue[0][2] =='L')
            bam.angle -= 90;
        else bam.angle += 90;

        rotateNum = 0;
        rotationValue.RemoveAt(0);
    }

    switch(bam.angle)
    {
        case 360: bam.angle = 0; break;
        case -90: bam.angle = 270; break;
    }
}

회전을 해야할 이동횟수를 나타내는 rotateTime변수와 rotateNum 변수를 비교해 같다면 

뒤의 문자를 비교해 L이면 왼쪽 R은 오른쪽으로 회전 후 rotateNum을 0으로 초기화하고 해당 회전값을 삭제한다.

수직 방향을 0도로 기준으로 해 360도를 사용하므로 360도는 0으로, 0도에서 왼쪽으로 회전 시 각이 음수로 될 수 있어 270도로 변환한다.

 

예제1,2번을 둘 다 테스트 해보았고 문제 출제자가 의도한대로 잘 된것 같은데 왜 실패했는지 알 수가 없다....

 

2023_10_13 실패

---

2023_10_17 시간초과

백준 홈페이지에서 문제를 다시 보다가 질문게시판을 찾게 되었다.

문제에서 제공된 예시말고 다른 사람들의 테스트 케이스를 입력하였더니

에러가 발생했다. 

딕셔너리는 비어있지만 Null은 아니다 

if (rotationValue == null) return;

이와 같은 에러처리는 잘못되었다. 

if (rotationValue.Count < 1) return;

이와같이 변경하고 들뜬 마음에 재제출을 해보았다. 하지만 실패... 

---

Move 함수에 로그를 찍어가며 어느 부분이 문제인지 확인해보았다. Bam클래스에 기준점인 int point 추가함. 

Console.WriteLine($"{body[moveCount-1].X- point} {body[moveCount - 1].Y - point} -> {this.x- point} {y-point}");

Rotate 함수에도 회전을 할 때마다 로그가 찍히도록 하고 테스트를 진행해보니 회전해야 할 이동횟수가 아스키 코드의 숫자범위(9)를 초과하면 회전 해야 할 때가 아닌데 회전하는것을 발견했다. 

 

정수와 문자를 어떻게 저장해 활용할지 고민하다가 처음에 생각했던 딕셔너리를 사용하기로 마음먹었다.

 

컴파일러에서 경고뜨는것이 보기 싫어서 입력 부분도 변경해주었는데 

가장 중요한 부분은 새롭게 추가한 변수인 rotateCount이다. 

입력받은 문자의 정수를 계속 추가해 몇번째에 회전을 해야하는지를 딕셔너리에 추가 할 수 있다. 

static Dictionary<int, char> rotationValue = new Dictionary<int, char>();
public static void Main()
{
    int.TryParse(Console.ReadLine(), out size);
    int.TryParse(Console.ReadLine(), out rotation);

    int rotateCount = 0;
    for (int i = 0; i < rotation; i++)
    {
        string? inputValue = Console.ReadLine();
        if (inputValue == null) return;
        string[] input = inputValue.Split();

        int inputCount = int.Parse(input[0]);
        rotateCount += inputCount;
        rotationValue.Add(rotateCount, char.Parse(input[1])) ;
        
        plate = 2 * size;
        
        Bam bam = new Bam(size);

        while(!IsDead(bam, plate))
        {
            if (rotationValue.ContainsKey(rotateNum) && rotationValue.Count < 1)
                Rotate(bam);
            bam.Move();
            rotateNum++;
        }

        Console.WriteLine(bam.moveCount);
}

 

List 자료형에서 Dictionary로 바꿔 Rotate함수도 깔끔해졌고, 예외처리 부분도 밖으로 빼 함수 이름에 맞게끔 회전만 담당하도록 하였다.

public static void Rotate(Bam bam)
{
    char dir = rotationValue[rotateNum];
    if (dir.Equals('L')) bam.angle -= 90;
    else bam.angle += 90;

    if (bam.angle == 360) bam.angle = 0;
    else if (bam.angle == -90) bam.angle = 270;
}

테스트 후 제출을 하였는데 이번에는 시간초과가 발생했다

 

IsDead함수에서 body를 순회하는 부분이 가장 오래 걸릴거 같아 이와 같이 변경했지만 결과는 같았다...

public class Bam
{
    public int x, y, moveCount, angle, point;

    public List<string> body = new List<string>();

    public Bam(int zeroPoint)
    {
        angle = 90;
        x = y = point = zeroPoint;
        moveCount = 0;
    }

    public void Move()
    {
        string bodyPoint = x.ToString() + y.ToString();
        body.Add(bodyPoint);
        switch (angle)
        {
            case 0: y += 1; break;
            case 90: x += 1; break;
            case 180: y -= 1; break;
            case 270: x -= 1; break;
        }
        moveCount++;
    }
}

public static bool IsDead(Bam bam, int plates)
{
    if (bam.moveCount < 1) return false;
    if (bam.x < 0 || bam.y < 0 || bam.x > plates || bam.y > plates)
        return true;

    else if (bam.body.Contains(bam.x.ToString() + bam.y.ToString()))
        return true;

    return false;
}

시간초과 문제를 해결하기 위해선 내 생각엔 예측을 해야할 것 같다. 

100000000
5
100000000 L
100000000 L
200000000 L
199999999 L
199999999 L

이 테스트 예제를 입력 했더니 몇분이 되어도 출력이 나오지 않았다.