경로 찾기 11403

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

문제가 이해하는데 좀 어렵기는 했다 "모든 정점 (i, j)에 대해서" 이문장에서 정점의 개념과 (i,j를 원소로 갖는) "정점의 개수 N" 문장에서 정점의 개념(1, 2, 3등의 숫자) 이 다른데 정점이라고 설명하다보니 헷갈리게 만든다.

위의 예제 같은 경우를 보자
3개의 노드가 있다. 1, 2, 3 이다

위의 행렬을 보자 행과 열의 인덱스는 다음과 같다
1,1 1,2 1,3
2,1 2,2 2,3
3,1 3,2 3,2

1,2 2,3 3,1 3개의 정점은 값이 1이므로 i노드에서 j노드로 연결된다는 뜻이다 다음과 같이 그릴 수 있다

순환이기 때문에 어디서 출발하든 어디든지 갈 수 있으므로
출력은
1 1 1
1 1 1
1 1 1
이다

ArrayList 이차원으로 연결관계를 저장하고

N X N 을 for문으로 돌면서
i행에서 j열로 연결되어 있는지
DFS 와 Stack 컬렉션을 사용해서 답을 구하고
true 면 1 false면 0을 출력하도록 해서 해결하였다

import java.io.*;
import java.util.*;

public class Main
{
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
        for(int i = 0; i <= N; ++i)
        {
            graph.add(new ArrayList<>());
        }

        String[] input;
        for(int i = 1; i <= N; ++i)
        {
            input = br.readLine().split(" ");
            for(int j = 1; j <= N; ++j)
            {
                int num = Integer.parseInt(input[j-1]);
                if(num == 1)
                    graph.get(i).add(j);
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int i = 1; i <= N; ++i)
        {
            for(int j = 1; j <= N; ++j)
            {
                if(dfs(i, j, graph, N))
                {
                    if(j == N)
                        sb.append(1);
                    else
                        sb.append(1 + " ");
                }
                else
                {
                    if(j == N)
                        sb.append(0);
                    else
                        sb.append(0 + " ");
                }

                if(j == N)
                    sb.append("\n");
            }
        }

        System.out.println(sb);
    }

    private static boolean dfs(int i, int j, ArrayList<ArrayList<Integer>> graph, int n)
    {
        Stack<Integer> stack = new Stack<>();

        stack.push(i);
        boolean[] visit = new boolean[n+1];
        visit[i] = true;

        while(stack.isEmpty() == false)
        {
            int cur = stack.peek();
            ArrayList<Integer> curNode = graph.get(cur);
            boolean noGo = true;
            for(int k = 0; k < curNode.size(); ++k)
            {
                int adj = curNode.get(k);
                if(adj == j)
                    return true;

                if(visit[adj] == true)
                    continue;

                stack.add(adj);
                visit[adj] = true;
                noGo = false;
                break;
            }

            if(noGo)
                stack.pop();
        }

        return false;
    }
}