글 읽기 - 19237 어른 상어 반례를 못찾겠습니다.

paraworld 3년 전 0

문제에서 하라는 대로 시뮬레이션했습니다.

예제는 당연히 다 넣어 봤고, 몇개 만들어 넣어 봤는데 문제 입력이 길어서 예시 하나 만들기 너무 힘드네요.

틀리는 케이스 또는 어떤 부분이 잘못되었는지 알려주시면 감사하겠습니다.

언어는 C#입니다.

using System;
using System.Collections.Generic;
using System.Linq;

// CapitalLetters for class names and methods, camelCase for variable names.
// Write your code clearly enough so that it doesn't need to be commented, or at least, so that it rarely needs to be commented.

namespace Testpad
{
    // 바라보는 방향
    public enum LookAt
    {
        up, down, left, right
    }

    public class BaekJoon19237
    {
        static void Main()
        {
            // 4방향 이동
            int[] moveX = new int[4] { 0, 0, -1, 1 };
            int[] moveY = new int[4] { -1, 1, 0, 0 };

            int turn = 0; // 현재 시간

            int[] inputs = Console.ReadLine().Split(" ").Select(int.Parse).ToArray();
            int n = inputs[0]; // n * n짜리 지도
            int m = inputs[1]; // 상어의 수
            int k = inputs[2]; // 냄새의 지속시간

            MapInfo[,] map = new MapInfo[n, n]; // 지도
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    map[j, i] = new MapInfo();
                }
            }

            SharkInfo[] sharks = new SharkInfo[m]; // 상어들의 정보
            for (int i = 0; i < m; i++)
            {
                sharks[i] = new SharkInfo();
                sharks[i].priorMove = new List<LookAt>[4];

                for (int j = 0; j < 4; j++)
                {
                    sharks[i].priorMove[j] = new List<LookAt>();
                }
            }

            // 지도를 받음
            for (int i = 0; i < n; i++)
            {
                inputs = Console.ReadLine().Split(" ").Select(int.Parse).ToArray();

                for (int j = 0; j < n; j++)
                {
                    // 상어가 있는 칸인 경우
                    if (inputs[j] > 0)
                    {
                        map[j, i].smellNumber = inputs[j];
                        map[j, i].duration = k;
                        map[j, i].posNumber = inputs[j];
                        sharks[inputs[j] - 1].x = j;
                        sharks[inputs[j] - 1].y = i;
                    }
                    // 빈칸인 경우
                    else
                    {
                        map[j, i].posNumber = 0;
                        map[j, i].smellNumber = 0;
                        map[j, i].duration = 0;
                    }
                }
            }

            // 상어들이 바라보는 방향을 받음
            inputs = Console.ReadLine().Split(" ").Select(int.Parse).ToArray();
            for (int i = 0; i < inputs.Length; i++)
            {
                sharks[i].currentLook = (LookAt)(inputs[i] - 1);
                // Console.WriteLine($"shark{i}, currentLook = {sharks[i].currentLook}"); // 디버그용
            }

            // 상어들의 방향 우선순위를 받음
            for (int i = 0; i < m; i++)
            {               
                for (int j = 0; j < 4; j++)
                {
                    inputs = Console.ReadLine().Split(" ").Select(int.Parse).ToArray();

                    for (int a = 0; a < inputs.Length; a++)
                    {
                        sharks[i].priorMove[j].Add((LookAt)(inputs[a] - 1));
                        // Console.WriteLine($"shark{i}, currentLook = {(LookAt)(j)}, prior{a}:{(LookAt)(inputs[a] - 1)}"); // 디버그용
                    }
                }
            }

            // 상어들을 이동시킴
            Dictionary<int, SharkInfo> dictionary = new Dictionary<int, SharkInfo>();

            // 처음 주어지는 상어들을 리스트에 추가
            for (int i = 0; i < sharks.Length; i++)
            {
                dictionary.Add(i, sharks[i]);
            }

            while (turn <= 1000 && dictionary.Count > 1)
            {
                turn++;
                // Console.WriteLine(turn + " " + dictionary.Count); // 디버그용
                int thisTime = dictionary.Count;

                for (int i = 0; i < thisTime; i++)
                {
                    // 중간에 제거시킨 상어는 무시함
                    if (dictionary.ContainsKey(i) == false)
                    {
                        continue;
                    }

                    bool moved = false; // 상어가 이동했는지 여부

                    // 현재 쳐다보는 방향을 기준으로, 4방향을 둘러봄
                    for (int j = 0; j < 4; j++)
                    {
                        int thisX = dictionary[i].x + moveX[(int)dictionary[i].priorMove[(int)dictionary[i].currentLook][j]];
                        int thisY = dictionary[i].y + moveY[(int)dictionary[i].priorMove[(int)dictionary[i].currentLook][j]];

                        try
                        {
                            // 냄새가 없는 칸이 있다면, 그쪽으로 상어를 이동시킴
                            if (map[thisX, thisY].smellNumber == 0)
                            {
                                map[dictionary[i].x, dictionary[i].y].posNumber = 0;

                                // 해당 위치에 여러 마리가 올 경우, 큰 번호를 제거함
                                if (map[thisX, thisY].posNumber != 0 && map[thisX, thisY].posNumber < i + 1)
                                {
                                    dictionary.Remove(i);
                                }
                                else if (map[thisX, thisY].posNumber > i + 1)
                                {
                                    dictionary.Remove(map[thisX, thisY].posNumber - 1);
                                    dictionary[i].currentLook = dictionary[i].priorMove[(int)dictionary[i].currentLook][j];
                                    dictionary[i].x = thisX;
                                    dictionary[i].y = thisY;
                                    map[thisX, thisY].posNumber = i + 1;
                                }
                                else
                                {
                                    dictionary[i].currentLook = dictionary[i].priorMove[(int)dictionary[i].currentLook][j];
                                    dictionary[i].x = thisX;
                                    dictionary[i].y = thisY;
                                    map[thisX, thisY].posNumber = i + 1;
                                }

                                moved = true;
                                break;
                            }
                        }
                        catch (IndexOutOfRangeException)
                        {

                        }
                    }

                    // 갈 곳이 없다면, 자신의 냄새가 있는 곳으로 이동시킴
                    if (moved == false)
                    {
                        for (int j = 0; j < 4; j++)
                        {
                            int thisX = dictionary[i].x + moveX[(int)dictionary[i].priorMove[(int)dictionary[i].currentLook][j]];
                            int thisY = dictionary[i].y + moveY[(int)dictionary[i].priorMove[(int)dictionary[i].currentLook][j]];

                            try
                            {
                                // 자기 냄새가 있는 칸으로 이동시킴
                                if (map[thisX, thisY].smellNumber == i + 1)
                                {
                                    map[dictionary[i].x, dictionary[i].y].posNumber = 0;
                                    dictionary[i].currentLook = dictionary[i].priorMove[(int)dictionary[i].currentLook][j];
                                    dictionary[i].x = thisX;
                                    dictionary[i].y = thisY;
                                    map[thisX, thisY].posNumber = i + 1;
                                    break;
                                }
                            }
                            catch (IndexOutOfRangeException)
                            {

                            }
                        }
                    }
                }

                // 맵의 냄새들 조정
                for (int i = 0; i < n; i++)
                {
                    for (int j = 0; j < n; j++)
                    {
                        if (map[j, i].duration > 0)
                        {
                            map[j, i].duration--;

                            // 냄새의 지속시간이 다했다면, 해당 칸을 빈칸으로 만듬
                            if (map[j, i].duration == 0)
                            {
                                map[j, i].smellNumber = 0;
                            }
                        }
                    }
                }

                foreach (var item in dictionary)
                {
                    map[item.Value.x, item.Value.y].smellNumber = item.Key + 1;
                    map[item.Value.x, item.Value.y].duration = k;
                    // Console.WriteLine($"Shark{item.Key}, Pos({item.Value.x}, {item.Value.y})"); // 디버그용
                }

                // 디버그용
                /* Console.WriteLine($"turn = {turn}");
                for (int i = 0; i < n; i++)
                {
                    for (int j = 0; j < n; j++)
                    {
                        Console.Write(map[j, i].posNumber + " ");
                    }
                    Console.WriteLine();
                } */
            }

            // 결과 출력
            // 1000턴이 지나도록 다른 상어가 남아 있다면, -1 출력
            if (turn > 1000)
            {
                Console.Write(-1);
            }
            // 아니면 턴수 출력
            else
            {
                Console.Write(turn);
            }
        }
    }

    // 상어들의 정보
    public class SharkInfo
    {
        // 상어의 좌표
        public int x { get; set; }
        public int y { get; set; }

        // 현재 바라보는 방향
        public LookAt currentLook { get; set; }
        // 현재 바라보는 방향에 따른 이동 우선순위
        public List<LookAt>[] priorMove { get; set; }
    }

    // 냄새의 정보
    public class MapInfo
    {
        // 해당 위치에 상어가 있다면, 상어의 번호. 없으면 0
        public int posNumber { get; set; }
        // 냄새의 번호
        public int smellNumber { get; set; }   
        // 해당 냄새의 남은 지속시간
        public int duration { get; set; }
    }
}

luniro 3년 전 0

초기 위치에서도 상어가 냄새를 뿌려야하는데 여기선 안 그러네요

paraworld 3년 전 0

초기 위치에서도 냄새를 뿌립니다.

map[j, i].smellNumber = inputs[j];
map[j, i].duration = k;
map[j, i].posNumber = inputs[j];

luniro 3년 전 0

앗 저는 217번째 줄의 foreach에 해당하는 부분을 while문 처음에 둬서, 따로 구현한 부분이 있을거란 생각을 못했네요

paraworld 3년 전 0

문제점 찾았습니다. 중간에 상어가 제거되었을 때, 남은 상어 수보다 큰 번호의 상어를 이동시키지 않은 걸 확인했습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

19237 어른 상어 반례를 못찾겠습니다.

paraworld 3년 전 0

luniro 3년 전 0

paraworld 3년 전 0

luniro 3년 전 0

paraworld 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말