글 읽기 - 어떻게 접근해야 시간 초과를 피할 수 있을까요?

paraworld 3년 전 0

16https://www.acmicpc.net/problem/1113

예전에 푼 문제와 동일한데 이 문제에서는 수의 범위가 커져서 높이가 낮은 곳부터 BFS 돌려서 물을 채워넣는 방법을 쓰니 시간 초과가 납니다.

어떻게 접근해야 할지 조언 부탁드립니다.

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 class BaekJoon15730
    {
        // 좌표
        struct Pos
        {
            public int x;
            public int y;

            public Pos(int x, int y)
            {
                this.x = x;
                this.y = y;
            }
        }

        static void Main()
        {
            Pos[] move = new Pos[4] { new Pos(0, 1), new Pos(1, 0), new Pos(-1, 0), new Pos(0, -1) }; // 물의 이동

            int[] inputs = Console.ReadLine().Split(" ").Select(int.Parse).ToArray();
            int x = inputs[1];
            int y = inputs[0];

            int[,] map = new int[x, y]; // 지도

            // 땅의 모양을 받음
            for (int i = 0; i < y; i++)
            {
                inputs = Console.ReadLine().Split(" ").Select(int.Parse).ToArray();

                for (int j = 0; j < x; j++)
                {
                    map[j, i] = inputs[j];
                }
            }

            // 높이가 낮은 순으로 물을 채워 보자
            Queue<Pos> queue = new Queue<Pos>();
            int[,] water = new int[x, y]; // 현재 물의 양

            for (int i = 0; i <= 10000; i++)
            {
                bool[,] used = new bool[x, y]; // 방문 체크

                // 가장자리는 볼 필요가 없음.
                for (int j = 1; j < y - 1; j++)
                {
                    for (int k = 1; k < x - 1; k++)
                    {
                        // 해당 위치가 적절하면, 물을 채워 넣음
                        if (map[k, j] <= i && used[k, j] == false)
                        {
                            bool leaking = false; // 물이 새는지 여부
                            List<Pos> vaildSpots = new List<Pos>(); // 인접한 곳들 중, 물을 담을 수 있는 좌표들 목록

                            queue.Clear();
                            queue.Enqueue(new Pos(k, j));
                            used[k, j] = true;
                            vaildSpots.Add(new Pos(k, j));

                            while (queue.Count > 0)
                            {
                                int thisTime = queue.Count;

                                for (int u = 0; u < thisTime; u++)
                                {
                                    for (int h = 0; h < 4; h++)
                                    {
                                        // 4방향을 확인
                                        try
                                        {
                                            int thisX = queue.Peek().x + move[h].x;
                                            int thisY = queue.Peek().y + move[h].y;

                                            // 높이가 같거나 낮고, 사용한 좌표가 아니면 큐에 추가
                                            if (map[thisX, thisY] <= i && used[thisX, thisY] == false)
                                            {
                                                queue.Enqueue(new Pos(thisX, thisY));
                                                used[thisX, thisY] = true;
                                                vaildSpots.Add(new Pos(thisX, thisY));
                                            }
                                        }
                                        // 배열을 벗어난다면, 해당 영역의 물은 죄다 새버린다는 소리이니 계산은 하되 종료시 해당 영역에 물을 채우지 않음
                                        catch (IndexOutOfRangeException)
                                        {
                                            leaking = true;
                                        }
                                    }


                                    queue.Dequeue();
                                }
                            }

                            // 물이 새지 않는다면, 해당 영역에 물을 채운다.
                            if (leaking == false)
                            {
                                foreach (var item in vaildSpots)
                                {
                                    water[item.x, item.y]++;
                                }
                            }
                        }
                    }
                }
            }

            // 채울 수 있는 물의 양을 출력
            int maxWater = 0;
            foreach (var item in water)
            {
                maxWater += item;
            }

            Console.Write(maxWater);
        }
    }
}

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

문제

문제

출처

ICPC

어떻게 접근해야 시간 초과를 피할 수 있을까요?

paraworld 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말