글 읽기 - C#) 메모리 초과가 납니다.

paraworld 3년 전 0

모든 빈칸에서 BFS 돌렸다가 바로 시간초과 나길래, 몇번 해보면서 생각해 보니 트리의 지름 문제랑 비슷한 것을 확인하고, 그렇게 풀었는데 메모리 초과가 뜹니다.

공간복잡도는 어떻게 계산해야 할지도 모르겠고, 인접 행렬을 인접 리스트로 만들자니 주어지는 지도가 2차원이라 어떻게 인접 리스트를 만들어야 할지 감이 안잡힙니다.

구글링해도 이 문제에 관한 자료는 죄다 C++이네요.

처음에 BFS 한번 돌려서 리프 노드들을 잡고 트리를 만든 다음, 임의의 리프 노드 하나로부터의 최장 거리에 있는 리프 노드를 기준점으로 잡아서

그 기준점에서 다른 리프 노드까지의 최장 거리를 구하는 식으로 풀었습니다.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
// using System.IO; // 디버그용

// 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
{
    // The ACM have found that two of the hooks must be connected by a rope that runs through the hooks in every block on the path between the connected ones.
    // When the rope is fastened, a secret door opens. The problem is that we do not know which hooks to connect.
    // 임의로 정한 두 빈칸의 최장 거리를 구하라는 문제임.

    // The labyrinth is designed in such a way that there is exactly one path between any two free blocks.
    // 모든 빈칸은 이어져 있고, 임의의 한 빈칸에서 다른 한 빈칸으로 가는 경로는 하나뿐임.

    // 이때, there is exactly one path between any two free blocks 라고 하니, 가장 가장자리에 있는 빈칸 2개를 이은 최장 거리만 구하면 됨.

    public class BaekJoon3482
    {
        // 미궁 내에서의 4방향 이동
        static int[] moveX = new int[4] { 1, -1, 0, 0 };
        static int[] moveY = new int[4] { 0, 0, 1, -1 };

        static char[,] map;
        static List<Pos>[,] paths;
        static Queue<Pos> queue = new Queue<Pos>();
        static bool[,] used;
        static int[,] distance;

        // 좌표
        struct Pos
        {
            public int x;
            public int y;

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

        static void Main()
        {
            StringBuilder sb = new StringBuilder();
            // StreamReader file = new StreamReader(@"C:\BOJ data\BOJ3282_Input.txt"); // 디버그용

            int t = int.Parse(Console.ReadLine()); // TC의 수 t
            // int t = int.Parse(file.ReadLine()); // 디버그용

            for (int i = 0; i < t; i++)
            {
                int maxDistance = 0; // 필요한 로프의 길이

                int[] inputs = Console.ReadLine().Split(" ").Select(int.Parse).ToArray();
                // int[] inputs = file.ReadLine().Split(" ").Select(int.Parse).ToArray(); // 디버그용
                int x = inputs[0]; // 가로 길이
                int y = inputs[1]; // 세로 길이

                map = new char[x, y]; // 주어지는 미궁 지도

                Pos blank = new Pos(-1, -1); // 임의의 빈칸의 좌표

                // 미궁 지도를 받음
                for (int j = 0; j < y; j++)
                {
                    char[] mazeInput = Console.ReadLine().ToCharArray();
                    // char[] mazeInput = file.ReadLine().ToCharArray(); // 디버그용

                    for (int k = 0; k < x; k++)
                    {
                        map[k, j] = mazeInput[k];

                        // 처음 들어오는 빈칸을 잡음
                        if (map[k, j] == '.')
                        {
                            blank = new Pos(k, j);
                        }
                    }
                }

                paths = new List<Pos>[x, y]; // 특정 정점에 연결된 길들 목록

                for (int j = 0; j < y; j++)
                {
                    for (int k = 0; k < x; k++)
                    {
                        paths[k, j] = new List<Pos>();
                    }
                }

                Pos pivot = new Pos(-1, -1); // 다음 기준점이 될 가장자리 칸 좌표

                // 우선 처음 들어오는 빈칸에서 BFS 한번 돌려서 가장자리 칸들 좌표를 얻고, 그래프를 만듬
                queue.Clear();
                used = new bool[x, y]; // 방문 체크

                // 첫 빈칸을 큐에 넣음
                queue.Enqueue(blank);
                used[blank.x, blank.y] = true;

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

                    for (int j = 0; j < thisTime; j++)
                    {
                        int nearByWalls = 0; // 바로 옆에 있는 칸의 벽 개수

                        // 4방향을 둘러보자. 이때, 빈칸에서 정확히 3방향이 벽이면 해당 빈칸은 가장자리 칸임.
                        for (int k = 0; k < 4; k++)
                        {
                            // 이번에 둘러볼 좌표
                            int thisX = queue.Peek().x + moveX[k];
                            int thisY = queue.Peek().y + moveY[k];

                            if (map[thisX, thisY] == '#')
                            {
                                nearByWalls++;
                            }
                            else if (map[thisX, thisY] == '.' && used[thisX, thisY] == false)
                            {
                                paths[queue.Peek().x, queue.Peek().y].Add(new Pos(thisX, thisY));
                                paths[thisX, thisY].Add(new Pos(queue.Peek().x, queue.Peek().y));
                                queue.Enqueue(new Pos(thisX, thisY));
                            }

                            used[thisX, thisY] = true;
                        }

                        // 가장자리 칸이면 기준점으로 잡음
                        if (nearByWalls == 3)
                        {
                            pivot = queue.Peek();
                        }

                        queue.Dequeue();
                    }
                }

                if (pivot.x != -1 && pivot.y != -1)
                {
                    // 임의의 한 가장자리 좌표에서 가장 먼 다른 가장자리 좌표를 기준점으로 잡음
                    queue.Clear();
                    used = new bool[x, y];
                    distance = new int[x, y];

                    // 임의의 가장자리 좌표를 큐에 넣음
                    queue.Enqueue(pivot);
                    distance[pivot.x, pivot.y] = 0;
                    used[pivot.x, pivot.y] = true;

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

                        for (int j = 0; j < thisTime; j++)
                        {
                            Pos current = queue.Peek(); // 이번 기준점

                            foreach (var position in paths[current.x, current.y])
                            {
                                // 방문한 좌표가 아니라면, 해당 지점까지의 거리 갱신
                                if (used[position.x, position.y] == false)
                                {
                                    distance[position.x, position.y] = distance[current.x, current.y] + 1;
                                    used[position.x, position.y] = true;
                                    queue.Enqueue(position);

                                    if (maxDistance < distance[position.x, position.y])
                                    {
                                        maxDistance = distance[position.x, position.y];
                                        pivot = position;
                                    }
                                }
                            }

                            queue.Dequeue();
                        }
                    }

                    // 기준점 좌표에서 가장 먼 좌표까지의 거리가 답임.
                    maxDistance = 0;

                    queue.Clear();
                    used = new bool[x, y];
                    distance = new int[x, y];

                    queue.Enqueue(pivot);
                    distance[pivot.x, pivot.y] = 0;
                    used[pivot.x, pivot.y] = true;

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

                        for (int j = 0; j < thisTime; j++)
                        {
                            Pos current = queue.Peek(); // 이번 기준점

                            foreach (var position in paths[current.x, current.y])
                            {
                                // 방문한 좌표가 아니라면, 해당 지점까지의 거리 갱신
                                if (used[position.x, position.y] == false)
                                {
                                    distance[position.x, position.y] = distance[current.x, current.y] + 1;
                                    used[position.x, position.y] = true;
                                    queue.Enqueue(position);

                                    if (maxDistance < distance[position.x, position.y])
                                    {
                                        maxDistance = distance[position.x, position.y];
                                    }
                                }
                            }

                            queue.Dequeue();
                        }
                    }
                }
                
                // 결과 저장
                sb.AppendLine("Maximum rope length is " + maxDistance.ToString() + ".");
            }

            // 결과 출력
            Console.Write(sb.ToString());
        }
    }
}

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

문제

문제

출처

ICPC

C#) 메모리 초과가 납니다.

paraworld 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말