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이다)
개발
백준은 멀티스레드가 막혀있어서 그럴겁니다