99클럽 코테 스터디 11일차 TIL : BFS/DFS(백준 25195번)

 

 

Yes or yes

 

 

 

 

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

 

 

 

---

⭐나의 풀이

 

💡 아이디어) 

 

DFS/BFS

 

 

✔ 최종 제출한 코드)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	private static List<Integer>[] graph;
	private static boolean[] visited;		//방문여부 
	private static Queue<Integer> queue;	//bfs 큐 
	private static Map<Integer, Integer> map;
	static boolean check = false;

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String str = br.readLine();
		StringTokenizer st = new StringTokenizer(str);
		int n = Integer.parseInt(st.nextToken()); //정점의 개수
		int m = Integer.parseInt(st.nextToken()); //간선의 개수
		
		graph = new ArrayList[n+1];
		visited = new boolean[n+1];
		queue = new LinkedList<>();
		
		for(int i=1;i<n+1;i++) {
			graph[i] = new ArrayList<>();
		}
		
		//간선정보 저장
		for(int i=1;i<m+1;i++) {
			str = br.readLine();
			st = new StringTokenizer(str);
			
			int p1 = Integer.parseInt(st.nextToken()); //정점1
			int p2 = Integer.parseInt(st.nextToken()); //정점2
			
			graph[p1].add(p2);
			//graph[p2].add(p1);
		}
		
		for(int i=1;i<n+1;i++) {
			Collections.sort(graph[i]);
		}
		
		int s = Integer.parseInt(br.readLine());	//곰곰이가 존재하는 정점갯수
		str = br.readLine();
		st = new StringTokenizer(str);
		
		map = new HashMap<>();
		
		for(int i=1;i<s+1;i++) {
			int p= Integer.parseInt(st.nextToken());
			map.put(p, 1);
		}
		
		if(map.containsKey(1)) {
			check = false;
		}else {
			bfs(1);
		}
		System.out.println(check ? "yes" : "Yes");
	}

	private static void bfs(int start) {
		visited[start] = true;	//방문
		queue.add(start);
		
		while(!queue.isEmpty()) {
			int newp = queue.poll();
			
			if(map.containsKey(newp)) continue;
			if(graph[newp].isEmpty()) {
				check = true ;
				return;
			}
			
			for(int p : graph[newp]) {
				if(visited[p]!=true) { 
					visited[p] = true;	//방문
					queue.add(p);
				}
			}
			
		}
		
	}

}

 

결과

걸린 시간: 2시간

---

 ⭐오늘의 회고

양방향으로 했다가 시간을 너무 많이 잡아먹었다.

양방향으로 하니 마지막 리프노드인지 확인하는 절차가 매우 까다롭게 느껴졌고,,

 

문제 다시 살펴보니 단방향이어서 코드를 다시 수정하는 시간을 가졌다.

단방향으로 하니 그래프가 저장된 리스트가 비어있는지 없는지만 확인하면 되서 쉽게 풀렸다 !