백준 13023번

13023번: ABCDE

 

문제를 읽어봤을 때 무슨 얘기인지 헷갈린다.

 

A부터 시작해서 E까지 친구관계가 '연속' 해야 한다.

5 연속하는 관계가 존재하는지 여부를 묻고있다.

 

생각하는 풀이

입력받은대로 그래프를 만들고 5연속이 가능한 지 탐색해보는 것.

 

 

링크:  [자료구조] 그래프 (Graph) - 인접행렬 vs 인접리스트, DFS, BFS, Connected Component, Spanning Tree

 

N은 정점의 갯수, M은 간선의 갯수

무방향 그래프

경로의 길이가 4 이상이 필요, 단순 경로.

노드와 간선의 관계로는 같은 숫자가 될 수 있으므로 인접 행렬과 인접 리스트 둘 다 사용 가능하다.

깊이가 5가 되는 경로를 찾는 조건이 있으므로 DFS를 실행하면 좋다. 인접행렬의 DFS 시간복잡도는 O(n²) 이며 인접 리스트로 구현하는 경우 DFS 시간복잡도는 O(n+e) 이다.

N과 M 최대 2,000의 값을 가질 수 있으니 인접행렬은 2000², 인접 리스트는 2,000+2,000이므로 인접 리스트를 이용하는 것이 좋다.

 

인접 리스트를 이용하여 그래프를 구현하고 DFS를 실행하여 단순 경로의 깊이가 5 이상을 만족하면 참을 반환한다.

 

 

틀린코드

namespace Coding_Test
{
    public class Node
    {
        private int id;
        private Node link;

        public Node(int id, Node link)
        {
            this.id = id;
            this.link = link;
        }

        public int Id
        {
            get { return id; }
            set { id = value; }
        }

        public Node Link
        {
            get { return link; }
            set { link = value; }
        }
    }

    // 무방향 그래프
    public class AdjacencyListGraph
    {
        protected const int MAX_VTXS = 2000;
        protected int size;
        protected char[] vertices;
        protected Node[] adjList;

        public AdjacencyListGraph()
        {
            size = 0;
            //vertices = new char[MAX_VTXS];
            adjList = new Node[MAX_VTXS];
        }

        public char GetVertex(int i)
        {
            return vertices[i];
        }

        public void Reset()
        {
            for ( int i = 0; i < size; ++i )
            {
                adjList[i] = null;
            }
            size = 0;
        }

        public void InsertVertex(int id)
        {
            if(IsFull())
            {
                Console.WriteLine("Graph vertex full error");
                return;
            }

            //vertices[size] = name;
            adjList[size++] = null;
        }

        public void InsertEdge(int u, int v)
        {
            adjList[u] = new Node(v, adjList[u]);
            adjList[v] = new Node(u, adjList[v]);
        }

        public Node Adjacent(int v)
        {
            return adjList[v];
        }

        public bool IsEmpty()
        {
            return size == 0;
        }

        public bool IsFull()
        {
            return size >= MAX_VTXS;
        }
        public void Display()
        {
            Console.WriteLine($"Vertex count: {size}");
            for (int i = 0; i < size; i++)
            {
                Console.Write($"{GetVertex(i)}: ");
                Node head = adjList[i];
                while ( head != null)
                {
                    Console.Write($"{GetVertex(head.Id)} ");
                    head = head.Link;
                }

                Console.WriteLine();
            }
        }
    }

    public class SearchAdjListGraph : AdjacencyListGraph
    {
        private bool[] visited = new bool[MAX_VTXS];

        public void ResetVisited()
        {
            for(int i = 0; i < size; ++i)
            {
                visited[i] = false; 
            }
        }

        public bool DFS()
        {
            for (int i = 0; i < size; ++i)
            {
                //Console.WriteLine($"{i} 인덱스 탐색 시작");
                ResetVisited();
                if(DFSRecur(i, 0, 5))
                {
                    return true;
                }
            }
            return false;
        }

        public bool DFSRecur(int v, int depth, int requireDepth)
        {
            ++depth;
            if (depth >= requireDepth)
            {
                return true;
            }

            visited[v] = true;
            //Console.WriteLine($"{v} 을/를 방문했습니다.");
            for (Node p = adjList[v]; p != null; p = p.Link)
            {
                if (visited[p.Id] == false) // 방문하지 않은 노드이면 true
                {
                    if(DFSRecur(p.Id, depth, requireDepth) )
                    {
                        return true;
                    }
                    else
                    {
                        visited[p.Id] = false;
                    }
                }
            }
            //Console.WriteLine($"{v} 을/를 백트래킹 합니다.");
            visited[v] = false;
            return false;
        }
    }


    public class CodingTest
    {

        public static void Main(string[] args)
        {
            string firstStr = Console.ReadLine();
            string[] firstStrs = SplitString(firstStr);
            int[] ints = StringToNum(firstStrs);
            
            int N = ints[0];
            int M = ints[1];

            SearchAdjListGraph graph = new SearchAdjListGraph();

            // 정점 삽입
            for ( int i = 0; i < N; ++i )
            {
                graph.InsertVertex( i );
            }

            // 간선 삽입
            for ( int i = 0; i < M; ++i )
            {
                string relationStr = Console.ReadLine();
                string[] relationStrs = SplitString(relationStr);
                int[] arr = StringToNum(relationStrs);
                
                int u = arr[0];
                int v = arr[1];

                graph.InsertEdge(u, v);
            }

            //graph.Display();

            if (graph.DFS())
            {
                Console.WriteLine(1);
            }
            else
            {
                Console.WriteLine(0);
            }
            
                 
        }

        // 한 줄에 여러개를 입력
        public static string[] SplitString(string input)
        {
            if (input.Contains(" "))
            {
                string[] _words = input.Split(' ');
                return _words;
            }
            else
            {
                string[] _words = new string[1];
                _words[0] = input;
                return _words;
            }
        }

        // str을 int등의 자료형으로 바꾸는 메서드
        public static int[] StringToNum(string[] words)
        {
            int[] result = new int[words.Length];
            for (int i = 0; i < words.Length; i++)
            {
                if(int.TryParse(words[i], out int num))
                {
                    result[i] = num;
                }
                else
                {
                    Console.WriteLine($"'{words[i]}'는 올바른 정수가 아닙니다.");
                    return null; // 또는 예외를 던질 수 있음
                }
            }
            return result;
        }

        // 나눌 필요 없는 숫자를 int로 바꾸는 메서드
        public static int OneStringToNum(string words)
        {
            int result = int.Parse(words);

            return result;
        }
    }
}

 

맞는 코드

using System;
using System.Collections.Generic;

namespace Coding_Test
{
    public class Node
    {
        private int id;
        private Node link;

        public Node(int id, Node link)
        {
            this.id = id;
            this.link = link;
        }

        public int Id
        {
            get { return id; }
            set { id = value; }
        }

        public Node Link
        {
            get { return link; }
            set { link = value; }
        }
    }

    public class AdjacencyListGraph
    {
        protected const int MAX_VTXS = 2000;
        protected int size;
        protected Node[] adjList;

        public AdjacencyListGraph()
        {
            size = 0;
            adjList = new Node[MAX_VTXS];
        }

        public void InsertVertex(int id)
        {
            if (IsFull())
            {
                Console.WriteLine("Graph vertex full error");
                return;
            }
            adjList[size++] = null;
        }

        public void InsertEdge(int u, int v)
        {
            adjList[u] = new Node(v, adjList[u]);
            adjList[v] = new Node(u, adjList[v]);
        }

        public bool IsFull()
        {
            return size >= MAX_VTXS;
        }
    }

    public class SearchAdjListGraph : AdjacencyListGraph
    {
        private bool[] visited = new bool[MAX_VTXS];
        private bool found = false;

        public bool DFS()
        {
            for (int i = 0; i < size; ++i)
            {
                Array.Clear(visited, 0, visited.Length);
                DFSRecur(i, 1);
                if (found) return true;
            }
            return false;
        }

        public void DFSRecur(int v, int depth)
        {
            if (depth == 5)
            {
                found = true;
                return;
            }

            visited[v] = true;

            for (Node p = adjList[v]; p != null; p = p.Link)
            {
                if (!visited[p.Id])
                {
                    DFSRecur(p.Id, depth + 1);
                    if (found) return;
                }
            }

            visited[v] = false;
        }
    }

    public class CodingTest
    {
        public static void Main(string[] args)
        {
            string[] firstStrs = Console.ReadLine().Split();
            int N = int.Parse(firstStrs[0]);
            int M = int.Parse(firstStrs[1]);

            SearchAdjListGraph graph = new SearchAdjListGraph();

            for (int i = 0; i < N; ++i)
            {
                graph.InsertVertex(i);
            }

            for (int i = 0; i < M; ++i)
            {
                string[] relationStrs = Console.ReadLine().Split();
                int u = int.Parse(relationStrs[0]);
                int v = int.Parse(relationStrs[1]);
                graph.InsertEdge(u, v);
            }

            Console.WriteLine(graph.DFS() ? 1 : 0);
        }
    }
}