BFS7 [ 백준 - 1043 ] 거짓말 - java 난이도 : G4Link : https://www.acmicpc.net/problem/1043Tag : 그래프, BFS 문제 탐색하기 - 지민이는 각 파티에 모두 참석해서 진실, 혹은 거짓된 이야기를 합니다.- 지민이는 거짓말 쟁이가 되면 안됩니다. 즉, 이미 진실된 이야기를 한 사람들에게는 항상 진실된 이야기를, 거짓된 이야기를 한사람들에게는 항상 거짓된 이야기를 전달해야합니다. - 이미 이야기를 들었었던 사람이 있다면 그사람이 알고있는대로 진실 or 거짓을 이야기해야합니다. 즉 해당 파티에 참여한 모든 사람들은 진실 혹은 거짓된 정보를 통일되게 알아야합니다.문제는, 그 후에 서로다른 이야기를 들은 사람들이 파티에 참석하면 거짓말 쟁이가 되어버립니다. 즉 처음부터 진실된 이야기를 할 사람들, 거짓된 이.. 2025. 6. 6. [ 백준 - 5567 ] 결혼 난이도 : S2Link : https://www.acmicpc.net/problem/5567Tag : 그래프, BFS 문제 탐색하기 - 친구 관계가 주어진다.- 상근이의 친구의 친구까지 초대한다.- 초대할 사람의 수를 구하여라 시도 1 ( 성공😲)떠오른 문제 해결 방법여기서 핵심은 친구의 친구까지만 초대한다는 것이었습니다.bfs를 이용하여 방문하되 ,depth가 2이하인 노드의 개수를 구하면 된다고 생각하였습니다. 시간복잡도⏰BFS의 시간복잡도 O(V + E)이므로 시간 제한 1초안에 충분히 해결할 수 있습니다.n (2 ≤ n ≤ 500)m (1 ≤ m ≤ 10000) 구현 방법 세부 구현 사항1. 주어진 값을 입력받는다. 2. depth 배열을 생성한후 -1로 모두 초기화한다.3. 1을 큐에 넣고,.. 2025. 5. 28. [ 백준 - 1260 ] DFS와 BFS 난이도 : S2Link : https://www.acmicpc.net/problem/1260Tag : Graph, DFS, BFS 문제 탐색하기 - 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하면된다.- 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 문제 자체는 단순하다. 그래프의 BFS와 DFS를 연습해보기 좋은 문제이기 때문에 선택하였다.시도 1 ( 성공 😲)떠오른 문제 해결 방법먼저 그래프는 인접 리스트로 구현하는것을 선택하였다.특정 정점에 연결된 모든 정점을 자주 확인해야하고, 일반적으로 E가 V^2보다 작기 때문이다. 먼저 DFS는 재귀로 구현하려고.. 2025. 5. 26. [ 백준 - 11724 ] 연결 요소의 개수 with 그래프 그래프 구현 방법 인접 행렬인접 리스트공간 복잡도O( V^2 )O( V+E )정점 u, v가 연결되어있는지 확인하는 시간 복잡도O( 1 )O( min(deg(u), deg(v) )정점 v와 연결된 모든 정점을 확인하는 시간 복잡도O(V)O( deg(V) )효율적인 상황두 점의 연결여부를 자주 확인할 때E가 V^2에 가까울 때특정 정점에 연결된 모든 정점을 자주 확인할 때E가 V^2보다 훨씬 작을 때 백준 문제 : 11724번. 연결 요소의 개수 난이도 : S2Link : https://www.acmicpc.net/problem/11724Tag : Graph 문제 탐색하기 - 방향 없는 그래프가 주어졌을 때, 연결 요소의 개수를 구하여라시도 1 ( 성공 😲)떠오른 문제 해결 방법이번 문제에서는 연결리스.. 2025. 5. 12. 이전 1 2 다음
