1267번 - 작업순서

문제의 저작권은 SW Expert Academy에 있습니다.

1. 문제
    1-1. 링크
    1-2. 문제 해석
2. 코드
3. 실행시간

 

 

 

---

 

 

1. 문제

1-1. 링크

SW Expert Academy

 

1-2. 문제 해석

• 방향을 역순으로 돌려서 DFS를 하는 방법
• 들어오는 경로가 존재하지 않는 정점을 하나씩 지워나가는 방법

이 문제는 위 두 가지 방법으로 풀 수 있다.

두 방법 다 사용해봤는데 개인적으로 첫 번째 방법이 코드가 깔끔하고 구현하기 쉬워서 첫 번째 방법에 대해 설명하려고 한다.

 

 

문제에서 주어진 작업순서

 

문제에서 예시로 주어진 작업 순서는 위와 같다.

DFS를 활용한 방법을 사용하기 위해서는 방향을 역순으로 돌려야 한다.

 

 

방향을 역순으로 돌린 작업순서

 

바로 이렇게 말이다!

그러고 나서 DFS를 하면 된다.

만약 더 이상 탐색을 할 수 없는(= 더 이상 경로가 없는) 정점에 도달하면 그 정점을 출력하면 된다.

시작 위치를 어디로 설정해도 상관없다.

예를 들어 '7'을 시작 지점으로 골랐다고 치자.

7 -> 2 -> 1 -> 4

4에서는 더 이상 탐색을 할 수 없기 때문에 출력하고 되돌아간다. 이때 방문 여부도 체크해준다.

1로 되돌아와서 봤더니 1도 역시 더 이상 탐색이 불가능하다. (4를 이미 방문했기 때문에)

1을 출력하고 방문 체크하고 되돌아간다

.

.

. 

(반복)

 

 

정점들 사이의 관계를 저장하는 (N+1) x (N+1) 짜리 배열

 

정점들 사이의 관계를 나타내는 데이터는 위와 같은 배열에 저장하면 된다.

0번 정점은 입력으로 주어지지 않기 때문에 편의상 비워두고 N+1 크기로 배열을 잡아주었다.

 

to는 현재 정점의 번호를 나타내고

load[to][0]은 현재 정점에서 이동할 수 있는 정점의 개수를 나타내며

load[to][1]은 현재 정점에서 이동할 수 있는 첫 번째 정점

load[to][2]은 현재 정점에서 이동할 수 있는 두 번째 정점

.

.

.

load[to][n]은 현재 정점에서 이동할 수 있는 n 번째 정점을 나타낸다.

 

 

 

• 주의할 점

주의해야 할 작업순서의 예시

 

분명히 로직이 맞는데 계속 테스트 케이스가 틀리다고 뜨면 위 예시를 의심해볼 만하다.

문제에서는 작업순서가 없는 작업에 대한 언급을 하지 않았다. (해줬으면 좋으려만)

즉, 위 예시처럼 먼저 선행되어야 하는 작업이 없는 3번 작업이 존재할 수 있다는 것이다.

이 3번 작업의 경우 출력되어야 할 결과의 어느 부분에 들어가도 상관없다.

단, 없으면 틀렸다고 뜬다. 6번 테스트 케이스의 119번 정점이 이런 경우이다.

 

나 같은 경우는 두 번째 풀이 방법에 방문 처리 없이 코드를 짰더니 위와 같은 예외 상황을 처리해주지 못했다.

 

 

2. 코드

public class Day5_1267_작업순서 {
	static StringBuilder sb = new StringBuilder();
	static int[][] load;
	static boolean[] visited; // 방문처리
	static int V; // 정점

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

		for (int tc = 1; tc <= 10; tc++) {
			sb.append("#" + tc);
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			V = Integer.parseInt(st.nextToken());
			st.nextToken(); // E
			load = new int[V + 1][V + 1];
			visited = new boolean[V + 1];

			st = new StringTokenizer(br.readLine(), " ");
			while (st.hasMoreTokens()) {
				int from = Integer.parseInt(st.nextToken());
				int to = Integer.parseInt(st.nextToken());

				load[to][0]++; // 연결된 정점의 개수 카운트 (+1)
				load[to][load[to][0]] = from; // 방향을 역순으로 돌려서 저장
			}

			for (int i = 1; i <= V; i++) {
				if (!visited[i]) {
					dfs(i);
				}
			}

			sb.append('\n');
		}
		System.out.println(sb.toString());
	}

	public static void dfs(int from) {
		for (int to = 1; to <= load[from][0]; to++) { // 연결된 경로의 개수만큼 반복
			if (!visited[load[from][to]]) { // 연결된 정점에 방문한 적이 없다면
				dfs(load[from][to]); // 탐색
			}
		}

		visited[from] = true;
		sb.append(" " + from);
	}
}

 

 

3. 실행시간

두 가지 방법의 실행결과

 

DFS 방식은 136ms가 나왔고

정점을 지워나가는 방식은 176ms가 나왔다.

내가 다시 복습하고 코드를 짜면서 최적화도 한 것 때문에 속도 차이가 난 것 같다. (원래는 비슷할 듯!)

그나저나 내 위쪽에 있는 천상계는... 내려올 생각을 안 하신다 😭 대단함...

 

 

 

 

 

---

💡 느낀 점

• DFS 문제를 여러 번 풀고 정리하다 보니까 진짜 느낌이 빡온다. 처음에 이해하기가 어렵지 막상 구현해놓고 보면 코드는 진짜 짧은데... 이젠 잘할 수 있을 것 같다.
• 맨날 DFS만 연습해서 어떡한담... BFS는... 이라고 생각하고 있었는데 다음 날 바로 배웠다지...

---