[백준, Graph, JAVA] P.11403 경로찾기

방향그래프인 것을 생각하고, DFS를 이용하여 해결하였습니다. 로직은 아래와 같이 생각했습니다.

1. 행렬에 값을 넣을때 1일 경우 해당 위치 값 x,y를 이용하여 Element객체를 만들어 Queue에 넣는다.

2. Queue에서 Element를 하나 꺼낸다. 해당 위치를 Root로 두고 y는 현재 위치 x는 다음 위치로 DFS 연산을 진행한다.

   -> DFS 연산은 가리키는 곳이 값이 1이면서 방문하지 않은 곳이면 Root의 next 위치에서 다음 next 값들을 1로 바꿔준다.(이동 가능함을 체크한다는 의미) 그렇지 않으면 종료

   -> 만약 Root값과 가리키는 값이 같으면 종료.

3. 그려진 맵을 출력 

아래에는 코드입니다.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static int[][] map;
	static Queue<Element> queue = new LinkedList<Element>();
	static int N;
	static boolean[] visited;

	public static void main(String[] args) {
		Scanner scr = new Scanner(System.in);

		N = scr.nextInt();
		map = new int[N][N];

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				int a = scr.nextInt();
				map[i][j] = a;

				if (map[i][j] == 1) {
					queue.add(new Element(j, i));
				}
			}
		}

		
		while (!queue.isEmpty()) {
			visited = new boolean[N];
			Element element = queue.poll();
			visited[element.x] = true;
			dfs(element.y, element.y, element.x);
		}

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}
	}

	public static void dfs(int root, int start, int next) {
		if(root == next) {
			return;
		}
		
		for (int i = 0; i < N; i++) {
			if (map[next][i] == 1 && !visited[i]) {
				visited[i] = true;
				map[root][i] = 1;
				dfs(root, next, i);
			}
		}
	}
}

class Element {
	int x, y;

	public Element(int x, int y) {
		this.x = x;
		this.y = y;
	}
}

이전에 풀었던 문제들을 다시 풀고 있는데 전에는 한번에 쉽게 풀었던 기록이 있는데 다시 푸니까 시간 초과 3번만에 다시 맞췄네요...

근본적으로 알고리즘을 풀기 위해 생각하는 방법이랑 좀더 깊이 생각하는 법이 부족한 것 같습니다. 하루에 30분 정도는 알고리즘 기초 강의 수강을 해야겠습니다.