C#, 백준 '2048(EASY)' (12100번) 멀티 스레딩으로 풀기

uknowitstimeto·2020년 6월 29일
0
using System;
using System.Collections.Generic;
using System.Text;
using System.Threading;
using System.Diagnostics;



namespace CSPRAC
{
    class ThreadData
    {
        public int[][] board;
        public readonly int N;
        public readonly int depth;
        public readonly bool isFirst = false;
        public Program pg;

        public ThreadData(int[][] board, int N, int depth, Program pg)
        {
            this.board = board;
            this.N = N;
            this.depth = depth;
            this.pg = pg;
        }
        
    }

    class Program
    {
        public int answer = 0;

        static int SumBoard(int[][] board, int dir, int N) //dir 시계방향,  (12 => 위쪽, 3=> 오른쪽, 6=> 아래쪽, 9=> 왼쪽)
        {
            int max = 0; 

            switch(dir)
            {
                case 3:
                    for (int i = 0; i < N; i++)
                        for (int j = N - 1; j > 0; j--)
                        {
                            if (board[i][j] != 0 && board[i][j - 1] == board[i][j])
                            {
                                board[i][j] += board[i][j - 1];
                                board[i][j - 1] = 0;
                                if (max < board[i][j])
                                    max = board[i][j];
                            }
                        }
                    break;

                case 6:
                    for (int j = 0; j < N; j++)
                        for (int i = N - 1; i > 0 ; i--)
                        {
                            if (board[i][j] != 0 && board[i][j] == board[i - 1][j])
                            {
                                board[i][j] += board[i - 1][j];
                                board[i - 1][j] = 0;
                                if (max < board[i][j])
                                    max = board[i][j];
                            }
                        }
                    break;

                case 9:
                    for(int i=0;i<N;i++)
                        for(int j=0;j<N-1;j++)
                        {
                            if(board[i][j]!=0 && board[i][j+1] == board[i][j])
                            {
                                board[i][j] += board[i][j + 1];
                                board[i][j + 1] = 0;
                                if (max < board[i][j])
                                    max = board[i][j];
                            }
                        }
                    break;

                case 12:
                    for (int j = 0; j < N; j++)
                        for (int i = 0; i < N - 1; i++)
                        {
                            if (board[i][j] != 0 && board[i][j] == board[i+1][j])
                            {
                                board[i][j] += board[i+1][j];
                                board[i+1][j] = 0;
                                if (max < board[i][j])
                                    max = board[i][j];
                            }
                        }
                    break;
            }

            return max;
        }

        static int SumAndTrim(int[][] board, int dir, int N)
        {
            TrimBoard(board, dir, N);
            int ret = SumBoard(board, dir, N);
            TrimBoard(board, dir, N);
            return ret;
        }

        static void TrimBoard(int [][] board, int dir, int N)
        {
            List<int> list = new List<int>(N);
            switch (dir)
            {
                case 3:
                    for (int i = 0; i < N; i++)
                    {
                        for (int j = N - 1; j >= 0 ; j--)
                        {
                            if (board[i][j] != 0)
                                list.Add(board[i][j]);
                        }

                        for (int j = N - 1; j >= 0; j--)
                        {
                            if (j >= N-list.Count)
                                board[i][j] = list[N - j - 1];
                            else
                                board[i][j] = 0;
                        }
                        list.Clear();
                    }
                    break;

                case 6:
                    for (int j = 0; j < N; j++)
                    {
                        for (int i = N - 1; i >= 0; i--)
                        {
                            if (board[i][j] != 0)
                                list.Add(board[i][j]);
                        }

                        for (int i = N - 1; i >= 0; i--)
                        {
                            if (i >= N-list.Count)
                                board[i][j] = list[N-i-1];
                            else
                                board[i][j] = 0;
                        }
                        list.Clear();
                    }
                    break;

                case 9:
                    for(int i=0;i<N;i++)
                    {
                        for (int j = 0; j < N; j++)
                        {
                            if (board[i][j] != 0)
                                list.Add(board[i][j]);
                        }

                        for(int j=0;j<N;j++)
                        {
                            if (j < list.Count)
                                board[i][j] = list[j];
                            else
                                board[i][j] = 0;
                        }
                        list.Clear();
                    }

                    break;

                case 12:
                    for (int j = 0; j < N; j++)
                    {
                        for (int i = 0; i < N; i++)
                        {
                            if (board[i][j] != 0)
                                list.Add(board[i][j]);
                        }

                        for (int i = 0; i < N; i++)
                        {
                            if (i < list.Count)
                                board[i][j] = list[i];
                            else
                                board[i][j] = 0;
                        }
                        list.Clear();
                    }
                    break;
            }
            
        }

        static void Solve(int[][] board, int N, int depth, Program pg)
        {
            if (depth == 0)
                return;

            int[][][] copiedBoards = new int[4][][];
            for(int i=0;i<4;i++)
            {
                copiedBoards[i] = CloneBoard(board, N);
                int sum = SumAndTrim(copiedBoards[i], 3*(i+1), N);                

                lock(pg)
                {
                    //Console.WriteLine($"thread {Thread.GetCurrentProcessorId()} for depth {depth} and dir {3 * (i + 1)} ");
                    //PrintBoard(copiedBoards[i], N);
                    if (sum > pg.answer)
                        pg.answer = sum;
                }
                Solve(copiedBoards[i], N, depth - 1, pg);
            }
        }

        static void SolveJob(object data)
        {
            if(data is ThreadData td)
            {
                Solve(td.board, td.N, td.depth, td.pg);
            }
        }

        static void ThreadSolve(int [][] board, int N, int depth, Program pg)
        {
            if (depth <= 0)
                return;

            int[][][] copiedBoards = new int[4][][];
            Thread[] ts = new Thread[4];
            for(int i=0;i<4;i++)
            {
                copiedBoards[i] = CloneBoard(board, N);
                int sum = SumAndTrim(copiedBoards[i], 3 * (i + 1), N);

                lock (pg)
                {
                    //Console.WriteLine($"thread {Thread.GetCurrentProcessorId()} for depth {depth} and dir {3 * (i + 1)} ");
                    //PrintBoard(copiedBoards[i], N);
                    if (sum > pg.answer)
                        pg.answer = sum;
                }
                
                ts[i] = new Thread(SolveJob);
                ts[i].Start(new ThreadData(copiedBoards[i], N, depth - 1, pg));
            }

            for (int i = 0; i < 4; i++)
                ts[i].Join();
        }

        static void PrintBoard(int[][] board, int N)
        {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < N; i++)
            {
                for (int j = 0; j < N; j++)
                {
                    sb.Append(board[i][j]); sb.Append(' ');
                }
                Console.WriteLine(sb.ToString());
                sb.Clear();
            }
            Console.WriteLine("--------------");
        }

        static int[][] CloneBoard(int[][] board, int N)
        {
            int[][] ret = new int[N][];
            for (int i = 0; i < N; i++)
            {
                ret[i] = new int[N];
                for (int j = 0; j < N; j++)
                    ret[i][j] = board[i][j];
            }
            return ret;
        }

        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            int[][] board = new int[N][];

            for (int i = 0; i < N; i++)
                board[i] = Array.ConvertAll(Console.ReadLine().Split(' '), s => { return int.Parse(s); });

            Program pg = new Program();

            for (int i = 0; i < N; i++)
                for (int j = 0; j < N; j++)
                    if (pg.answer < board[i][j])
                        pg.answer = board[i][j];
            Stopwatch sw = new Stopwatch();
            sw.Start();
            ThreadSolve(board, N,  10, pg);         
            sw.Stop();
            Console.WriteLine($"4-ThreadSolve TIME TAKEN : {sw.ElapsedMilliseconds}ms");
            Console.WriteLine($" Answer : {pg.answer}");

            sw.Start();
            Solve(board, N, 10, pg);
            sw.Stop();
            Console.WriteLine($"SINGLE-ThreadSolve TIME TAKEN : {sw.ElapsedMilliseconds}ms");
            Console.WriteLine($" Answer : {pg.answer}");
            return;
        }
    }
}

4방향씩 재귀적으로 탐색해 나가며 모든 경우의수를 완전탐색해 문제를 풀었다.

멀티 쓰레드의 경우 처음 4방향 탐색시 각각 쓰레드를 할당해 4개의 쓰레드를 사용해 풀었다.

성능차이를 보다 쉽게 보기 위해, N=20 문제와 달리 5번이 아닌 10번 수행시 최댓값을 얻을 수 있도록 했다.

4쓰레드를 사용했을 땐, 4364ms
1쓰레드를 사용했을 땐, 17760ms 가 소요되었다.

멀티 쓰레딩이 더 빨리 풀거라 생각했지만 4배까지 차이가 날 줄은 몰랐다. 아마 쓰레드를 더 많이 썻으면 훨씬 더 빨라졌을 것이다.

그런데 백준 서버에서는 멀티쓰레딩 쓴게 더 오래 걸린다. 아무래도 환경이 차이나서 그런 것 같다. (참고로 내 CPU는 라이젠 3600이다)

profile
백수

0개의 댓글