개발자 톡

연습문제 톡 [HSAT 6회 정기 코딩 인증평가 기출] 출퇴근길

반례 알려주시면 정말 감사하겠습니다. 소프티어 유튜브 풀이 영상 보고 구현 해봤는데 통과가 안되서요 ㅠㅠ

등록일
2024-02-15 01:13:47
조회수
890
작성자
castela0119
import java.io.*;
import java.util.*;


public class Main {


    static int N; // 정점의 갯수
	static int M; // 간선의 갯수
	
	static ArrayList<Integer>[] graph1; // 정순
	static ArrayList<Integer>[] graph2; // 정순
	
	static boolean[] visited1; // 정순 S출발
	static boolean[] visited2; // 정순 T출발
	
	static boolean[] visitedR1; // 역순 S출발
	static boolean[] visitedR2; // 역순 T출발
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		graph1 = new ArrayList[N+1];
		graph2 = new ArrayList[N+1];
		
		visited1 = new boolean[N+1];
		visited2 = new boolean[N+1];
		visitedR1 = new boolean[N+1];
		visitedR2 = new boolean[N+1];
		
		for(int i=0; i<N+1; i++) {
			graph1[i] = new ArrayList<>();
			graph2[i] = new ArrayList<>();
		}
		
		for(int i=0; i<M; i++) {
			
			st = new StringTokenizer(br.readLine());
			
			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());
			
			graph1[A].add(B); // 정순 graph
			graph2[B].add(A); // 역순 graph
		}
		
		st = new StringTokenizer(br.readLine());
		
		int S = Integer.parseInt(st.nextToken());
		int T = Integer.parseInt(st.nextToken());
		
		iterative_BFS(S, T);
		iterative_BFS2(S, T);
		iterative_BFS_R1(S, T);
		iterative_BFS_R2(S, T);
		
		int cnt = 0;
		
		for(int i=0; i<N+1; i++) {
			if(visited1[i] == true && visited2[i] == true && visitedR1[i] == true && visitedR2[i] == true && i != S && i != T) {
				cnt += 1;
			}
			
		}
		
		System.out.println(cnt);
		
		
	}
	
	public static void iterative_BFS(int start, int end) {
		
		Queue<Integer> q = new LinkedList<>();
		q.add(start);
		visited1[start] = true;
		visited1[end] = true;
		
		while(!q.isEmpty()) {
			
			int v = q.poll();
			
			for(int w : graph1[v]) {
				
				if(visited1[w] == false) {
					q.add(w);
					visited1[w] = true;
				}
			}
		}
	}
	
	public static void iterative_BFS2(int start, int end) {
		
		Queue<Integer> q = new LinkedList<>();
		q.add(end);
		visited2[end] = true;
		visited2[start] = true;
		
		while(!q.isEmpty()) {
			
			int v = q.poll();
			
			for(int w : graph1[v]) {
				
				if(visited2[w] == false) {
					q.add(w);
					visited2[w] = true;
				}
			}
		}
	}
	
	public static void iterative_BFS_R1(int start, int end) {
		
		Queue<Integer> q = new LinkedList<>();
		q.add(start);
		visitedR1[start] = true;
		visitedR1[end] = true;
		
		while(!q.isEmpty()) {
			
			int v = q.poll();
			
			for(int w : graph2[v]) {
				
				if(visitedR1[w] == false) {
					q.add(w);
					visitedR1[w] = true;
				}
			}
		}
	}
	
	public static void iterative_BFS_R2(int start, int end) {
		
		Queue<Integer> q = new LinkedList<>();
		q.add(end);
		visitedR2[end] = true;
		visitedR2[start] = true;
		
		while(!q.isEmpty()) {
			
			int v = q.poll();
			
			for(int w : graph2[v]) {
				
				if(visitedR2[w] == false) {
					q.add(w);
					visitedR2[w] = true;
				}
			}
		}
	}
}


#[HSAT_6회_정기_코딩_인증평가_기출]_출퇴근길

이 카테고리의 톡 더보기