게임 개발자가 되고 싶어요

https://www.acmicpc.net/problem/23796

접근 방법

입력받은 배열을 UDLR에 맞게 하나하나 비교해가며 같으면 더하고, 아니면 넘어가는 형식으로 리스트 배열에 추가하여 치우치는 곳을 기준으로 출력하였다.

문제 풀이

- L 기준

• int형으로는 2147483647까지 받을 수 있으니 long으로 배열, List배열 선언.
• choose 정수를 선언 후, 0이면 그 값으로 선정
• choose가 0이 아니면 비교할 대상이 있는 것
  • 열의 값이 0이 아닐 때 choose와 값이 같으면 합칠 수 있으니 리스트에 choose*2 추가, 합쳐졌으니 choose는 0
  • 같지 않으면 서로 합치지 못하니 리스트에 choose 추가, 못합쳤으니 choose는 배열의 값으로
• 한 행이 탐색이 끝나면 choose가 0이 아니면 합쳐지지 못한 값이므로 출력을 위해 리스트에 추가
• 리스트의 크기가 8이 될 때까지 0을 추가해줌

1. R은 열 인덱스를 반대로 탐색 후 리스트 뒤집어 주기
2. U는 행과 열을 뒤집어서 탐색
3. D는 U탐색에서 행 인덱스를 반대로 탐색 후 뒤집기

• U와 D는 리스트가 가로로 되있으니 출력할 때는 세로로 출력
• L과 R은 그대로 출력

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

namespace Baekjoon.Gold
{
    class _23796
    {
        static void Main(string[] args)
        {
            StringBuilder stb = new StringBuilder();

            long[][] arr = new long[8][];
            for (int i = 0; i < 8; i++)
                arr[i] = Array.ConvertAll(Console.ReadLine().Split(), long.Parse);

            string s = Console.ReadLine();// 입력

            List<long>[] move = new List<long>[8];
            for (int i = 0; i < 8; i++)
                move[i] = new List<long>();

            if(s == "U")
            {
                for(int i = 0; i < 8; i++)
                {
                    long choose = 0;
                    for(int j = 0; j<8; j++)
                    {
                        if (choose == 0)
                            choose = arr[j][i];
                        else
                        {
                            if (arr[j][i] != 0)
                            {
                                if (choose == arr[j][i])
                                {
                                    move[i].Add(choose * 2);
                                    choose = 0;
                                }
                                else
                                {
                                    move[i].Add(choose);
                                    choose = arr[j][i];
                                }
                            }
                        }
                    }

                    if (choose != 0)
                        move[i].Add(choose);

                    while (move[i].Count < 8)
                        move[i].Add(0);
                }
            }
            else if (s == "D")
            {
                for (int i = 0; i < 8; i++)
                {
                    long choose = 0;
                    for (int j = 7; j >= 0; j--)
                    {
                        if (choose == 0)
                            choose = arr[j][i];
                        else
                        {
                            if (arr[j][i] != 0)
                            {
                                if (choose == arr[j][i])
                                {
                                    move[i].Add(choose * 2);
                                    choose = 0;
                                }
                                else
                                {
                                    move[i].Add(choose);
                                    choose = arr[j][i];
                                }
                            }
                        }
                    }

                    if (choose != 0)
                        move[i].Add(choose);

                    while (move[i].Count < 8)
                        move[i].Add(0);

                    move[i].Reverse();
                }
            }
            else if (s == "L")
            {
                for(int i = 0; i < 8; i++)
                {
                    long choose = 0;
                    for(int j = 0; j<8; j++)
                    {
                        if (choose == 0)
                            choose = arr[i][j];
                        else
                        {
                            if (arr[i][j] != 0)
                            {
                                if (choose == arr[i][j])
                                {
                                    move[i].Add(choose * 2);
                                    choose = 0;
                                }
                                else
                                {
                                    move[i].Add(choose);
                                    choose = arr[i][j];
                                }
                            }
                        }
                    }

                    if (choose != 0)
                        move[i].Add(choose);

                    while (move[i].Count < 8)
                        move[i].Add(0);
                }
            }
            else
            {
                for(int i = 0; i<8; i++)
                {
                    long choose = 0;
                    for(int j = 7; j>=0; j--)
                    {
                        if (choose == 0)
                            choose = arr[i][j];
                        else
                        {
                            if (arr[i][j] != 0)
                            {
                                if (choose == arr[i][j])
                                {
                                    move[i].Add(choose * 2);
                                    choose = 0;
                                }
                                else
                                {
                                    move[i].Add(choose);
                                    choose = arr[i][j];
                                }
                            }
                        }
                    }

                    if (choose != 0)
                        move[i].Add(choose);

                    while (move[i].Count < 8)
                        move[i].Add(0);

                    move[i].Reverse();
                }
            }

            if(s == "U" || s == "D")
            {
                for(int i = 0; i<8; i++)
                {
                    for(int j = 0; j<8; j++)
                        stb.Append($"{move[j][i]} ");

                    stb.AppendLine();
                }
            }
            else
            {
                for(int i = 0; i< 8; i++)
                    stb.AppendLine(string.Join(" ", move[i]));
            }

            Console.WriteLine(stb);
        }
    }
}

https://www.acmicpc.net/problem/1916

접근 방법

아주 간단한 다익스트라 문제였다. 입력받은 간선의 정보로 그래프를 그리고 다익스트라를 구현하여 가야하는 곳의 최소비용을 구하였다.

문제 풀이

• 입력받은 노선들을 리스트 배열로 (다음 지점, 가중치) 그래프를 만들기
• 탐색확인용 visited, 탐색 가중치를 넣을 distance 배열을 생성 -> distance배열의 초기값에는 버스의 개수*최대가중치값을 넣어줌
• 우선순위 큐로 다익스트라를 구현하여, 현재 dequeue 된 지점이 탐색하지 않았을 경우 그 점에 연결된 노드 들을 탐색하며 가중치를 비교 -> 작은것을 세트 후, 우선순위 큐에 다시 넣어주기
• 탐색이 끝나고, distance 가야할 곳의 인덱스 값 출력

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

namespace Baekjoon.Gold
{
    class _1916
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            int m = int.Parse(Console.ReadLine());
            List<(int, int)>[] graph = new List<(int, int)>[n+1];
            for (int i = 1; i <= n; i++)
                graph[i] = new List<(int, int)>();

            for(int i = 0; i<m; i++)
            {
                int[] arr = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                graph[arr[0]].Add((arr[1], arr[2]));
            }

            //시작, 종점
            int[] togo = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

            bool[] visited = new bool[n + 1]; //탐색했는지
            int[] distance = Enumerable.Repeat(100000000, n + 1).ToArray(); //가중치
            PriorityQueue<int, int> pq = new PriorityQueue<int, int>(); //(다음탐색점, 가중치)
            pq.Enqueue(togo[0], 0);
            distance[togo[0]] = 0;

            //다익스트라
            while(pq.Count > 0)
            {
                int point = pq.Dequeue();
                if (!visited[point])
                {
                    visited[point] = true;

                    foreach((int, int) next in graph[point])
                    {
                        distance[next.Item1] = Math.Min(distance[next.Item1], next.Item2 + distance[point]);
                        pq.Enqueue(next.Item1, distance[next.Item1]);
                    }
                }
            }

            Console.WriteLine(distance[togo[1]]);
        }
    }
}

https://www.acmicpc.net/problem/1238

접근 방법

시작점과 일정한 종점이 주어졌으므로 다익스트라 알고리즘을 사용하였다. 학생마다 집 → 종점 + 종점→ 집의 거리를 구해 가장 오래 걸리는 것이 답.

문제 풀이

• 다익스트라를 사용하기위해 리스트로 그래프 만들기
• 우선순위 큐로 (탐색 지점, 가중치)를 넣고, 그래프 내의 현재 탐색 지점에서 갈 수 있는 곳의 가중치를 비교 후, 최솟값으로 다시 큐에 넣어주기
• 1번 학생부터 N번 학생까지 반복문으로 다익스트라를 사용하여 집 → X, X → 집의 거리를 구한 뒤 합, 학생중 최대값을 ans 에 저장
• ans 출력

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

namespace Baekjoon.Gold
{
    class _1238
    {
        static List<(int, int)>[] graph;
        static int v;

        static void Main(string[] args)
        {
            int[] n = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            v = n[0];
            int x = n[2];

            graph = new List<(int, int)>[v + 1];
            for (int i = 1; i <= v; i++)
                graph[i] = new List<(int, int)>();

            for (int i = 0; i < n[1]; i++)
            {
                int[] arr = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                graph[arr[0]].Add((arr[1], arr[2]));
            }


            int ans = 0;
            for(int i = 1; i<= v; i++)
            {
                int go = dijkstra(i, x);
                int back = dijkstra(x, i);

                ans = Math.Max(ans, go + back);
            }

            Console.WriteLine(ans);

        }

        static int dijkstra(int start, int end)
        {
            bool[] visited = new bool[v + 1];

            int[] distance = Enumerable.Repeat(1000001, v + 1).ToArray();
            PriorityQueue<int, int> pq = new PriorityQueue<int, int>();
            pq.Enqueue(start, 0);
            distance[start] = 0;

            while (pq.Count > 0)
            {
                int point = pq.Dequeue();

                if (!visited[point])
                {
                    visited[point] = true;

                    foreach ((int, int) next in graph[point])
                    {
                        distance[next.Item1] = Math.Min(distance[next.Item1], distance[point] + next.Item2);
                        pq.Enqueue(next.Item1, distance[next.Item1]);
                    }
                }
            }

            return distance[end];
        }
    }
}

https://www.acmicpc.net/problem/1956

접근 방법

시작점이 주어지지 않았고 종점에서 다시 시작점으로 돌아가야되니 모든 정점에서 최단거리를 찾는 플로이드-워셜 알고리즘을 사용했다.

문제 풀이

• 단방향 노선에 최대 정점의 개수가 400, 최대 가중치가 10000이니 inf를 40000001로 설정
• 입력받은 노선을 제외하고 나머지 노선들을 inf로 채우기
• 플로이드-워셜 알고리즘을 사용하여 각 점들에서의 최소값 찾기
• 반복문을 돌며 노선 중 inf가 아닐 때, 출발 i->j 노선과 되돌아가는 j->i 노선(사이클)의 합의 최소값을 ans에 저장
• 만약 ans가 inf면 사이클이 없는것이니 -1, 아니면 사이클이 있으므로 ans 출력

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

namespace Baekjoon.Gold
{
    class _1965
    {
        static int inf = 4000001;
        static void Main(string[] args)
        {
            //0 - 정점, 1 - 간선
            int[] n = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            int[][] graph = new int[n[0]+1][];
            for (int i = 1; i <= n[0]; i++)
                graph[i] = Enumerable.Repeat(inf, n[0] + 1).ToArray();

            for(int i = 0; i < n[1]; i++)
            {
                int[] m = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                graph[m[0]][m[1]] = m[2];
            }

            //플로이드 - 워셜
            for(int mid = 1; mid <= n[0]; mid++) //거침
            {
                for(int i = 1; i <= n[0]; i++) //출발
                {
                    for(int j = 1; j <= n[0]; j++) //도착
                        graph[i][j] = Math.Min(graph[i][j], graph[i][mid] + graph[mid][j]);
                }
            }

            int ans = inf;
            for(int i = 1; i <= n[0]; i++)
            {
                for(int j =1; j <= n[0]; j++)   
                {
                    if (i == j)
                        continue;

                    if (graph[i][j] != inf && graph[j][i] != inf)
                        ans = Math.Min(ans, graph[i][j] + graph[j][i]);
                }
            }

            if (ans != inf)
                Console.WriteLine(ans);
            else
                Console.WriteLine(-1);
        }
    }
}