백준 C# - 7576 +) 풀이

문제에 최소가 들어가면 BFS와 관련된 확률이 높다.

 

들어가기 앞서 주의!

01 그래프 (0,0)부터 입력받기

DFS, BFS문제에서 음수가 되는 경우를 배제하기 위해서 그래프값을 (1,1)을 넣으면서 진행하였는데 여기서는 그렇게 하면 안된다. 원인이 이거인지 모르고 열심히 그리다가 시간을 많이 소모하였다.. 하ㅏㅎㅏ..

 

앞으로 (0,0)에 넣고 조건문을 넣어 푸는게 좋을 것 같다는 생각이 들었다. 

---

 

02 string에 어떤 값이 들어가는지 꼭 확인하기

string문을 입력받으면 띄어쓰기 까지 입력이 받아진다.

string s = Console.ReadLine()

그래서 Replace를 사용해서 띄어쓰기를 삭제했다.

string s = Console.ReadLine().Replace(" ","");

그랬더니 -1이 "-1"로 인식이 되지 않고 '-','1'각각 인식을 하였다. 그래서 한번더 Replace를 사용하여 -1을 -로 바꾸어 주었다.

string s2 = s.Replace("-1", "-");

---

BFS알고리즘

BFS알고리즘은 앞서 풀었던 문제들과 비슷하다.

while (queue.Count>0)
{
    Tuple<int, int> now = queue.Dequeue();
    for (int i = 0; i < 4; i++)
    {
        int newX = now.Item1 + dirX[i];
        int newY = now.Item2 + dirY[i];
        if (newX >= N  || newY >= M || newX<0 || newY<0 || graph[newX,newY]<-1)
            continue;
        if (graph[newX, newY] == 0)
        {     
            graph[newX, newY] = graph[now.Item1, now.Item2] + 1;
            queue.Enqueue(new Tuple<int, int>(newX, newY));
        }
    }
}

---

출력 부분

대신 이 문제에서는 출력부분에 조건이 붙어서 이것만 처리해주면 된다.

01 그래프에 0이있는지 체크하는 메서드 추가

static bool checkZero()
{
    for(int i = 0; i<N; i++)
    {
        for(int j = 0; j<M; j++)
        {
            if (graph[i, j] == 0)
                return true;
        }
    }
    return false;
}

---

02 모두 익을때까지 최소 날짜 구하기

만약 0이있으면 -1, 아닐 경우 비교를 통해 최대 날짜 구하기

int max = -1;
if (checkZero()) return -1;
for (int i = 0; i < N; i++)
{
    for (int j = 0; j < M; j++)
    {
        max = Math.Max(max, graph[i, j]);
    }
}
return max-1; // 첫번째날 빼기

---

코드 전문

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

namespace baek2
{
   
    class Program
    {
        static int[] dirX = { 1, -1, 0, 0 };
        static int[] dirY = { 0, 0, 1, -1 };
        static int N,M;
        static int[,] graph = new int[1011,1011];
        static Queue<Tuple<int,int>> queue = new Queue<Tuple<int,int>>();

        static bool checkZero()
        {
            for(int i = 0; i<N; i++)
            {
                for(int j = 0; j<M; j++)
                {
                    if (graph[i, j] == 0)
                        return true;
                }
            }
            return false;
        }
        static int BFS()
        {
            while (queue.Count>0)
            {
                Tuple<int, int> now = queue.Dequeue();
                for (int i = 0; i < 4; i++)
                {
                    int newX = now.Item1 + dirX[i];
                    int newY = now.Item2 + dirY[i];
                    if (newX >= N  || newY >= M || newX<0 || newY<0 || graph[newX,newY]<-1)
                        continue;
                    if (graph[newX, newY] == 0)
                    {     
                        graph[newX, newY] = graph[now.Item1, now.Item2] + 1;
                        queue.Enqueue(new Tuple<int, int>(newX, newY));
                    }
                }
            }
            int max = -1;
            if (checkZero()) return -1;
            for (int i = 0; i < N; i++)
            {
                for (int j = 0; j < M; j++)
                {
                    max = Math.Max(max, graph[i, j]);
                }
            }
            return max-1;

        }
        public static void Main()
        {
            int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            M = input[0];
            N = input[1];

            for (int i = 0; i < N; i++)
            {
                string s = Console.ReadLine().Replace(" ","");
                string s2 = s.Replace("-1", "-");
                int index = 0;
                foreach (char c in s2)
                {
                    graph[i, index] = s2[index] - '0';
                    if (graph[i, index] == 1)
                    {
                        queue.Enqueue(new Tuple<int, int>(i, index));
                    }
                    index++;
                }      
            }

            Console.Write(BFS());
        }
    }
}