💻 백준 1260: DFS와 BFS
시작하기에 앞서
이번 문제는 다른 분의 코드를 짜깁기하다시피 해서 푼 문제이다.
급한데 머리가 안굴러가서 어떻게든 일단 하는 것을 목적으로 잡았기 때문이다.
참고
⭐[자료구조/Java] Graph 검색 DFS, BFS 구현
[Java] Comparator/ compare 에 대하여 알아보자!
.
.
.
.
.
.
START!
문제
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.
입력
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
출력
첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.
코드
graph 클래스에 dfs, bfs 포함
인접한 노드에 대해서 sort하는 sortAdj(), visitReset() 메소드 제외하고는 ⭐표시의 블로그와 거의 동일하다.
class Graph {
class Node {
int data;
LinkedList<Node> adj;
boolean visited;
/* 노드 생성자 */
Node(int data) {
this.data = data;
this.visited = false;
adj = new LinkedList<Node>();
}
}
Node[] nodes;
/* 그래프 생성자 */
Graph(int init) {
nodes = new Node[init+1];
/* 0번 노드 사용하지 않는다 */
for (int i = 0; i < init + 1; i++) {
nodes[i] = new Node(i);
}
}
void addEdge(int i1, int i2) {
Node n1 = nodes[i1];
Node n2 = nodes[i2];
if (!n1.adj.contains(n2))
n1.adj.add(n2);
if (!n2.adj.contains(n1))
n2.adj.add(n1);
}
/* 인접 노드 sort */
void sortAdj() {
for(int i = 1; i < nodes.length; i++) {
nodes[i].adj.sort(new Comparator<Node>() {
@Override
public int compare(Node o1, Node o2) {
return o1.data > o2.data ? 1 : -1;
}
});
}
}
void printGraph() {
for(int i = 1; i < nodes.length; i++) {
System.out.print(i + ": ");
for(Node j : nodes[i].adj) {
System.out.print("->"+j.data);
}System.out.println();
}
}
void dfsRe(Node r) {
r.visited = true;
visit(r);
for(Node n : r.adj) {
if(!n.visited)
dfsRe(n);
}
}
void dfs(int index) {
Node root = nodes[index];
dfsRe(root);
}
void bfs(int index){
Node root = nodes[index];
Queue<Node> queue = new LinkedList<>();
queue.add(root);
root.visited = true;
while(!queue.isEmpty()){
Node r = queue.poll();
for(Node n : r.adj){
if(n.visited == false){
n.visited = true;
queue.add(n);
}
}
visit(r);
}
}
void visitReset() {
for(Node n : nodes)
n.visited = false;
}
void visit(Node n) {
System.out.print(n.data + " ");
}
}N, M, V를 받아 edge 추가, 인접노드 sort 후에 dfs, bfs 실행한다.
public class Boj220311_dfsbfs {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
int V = sc.nextInt();
Graph gr = new Graph(N);
for(int i = 0; i < M; i++) {
int n1 = sc.nextInt();
int n2 = sc.nextInt();
gr.addEdge(n1, n2);
}
gr.sortAdj();
gr.dfs(V);
gr.visitReset();
System.out.println();
gr.bfs(V);
}
}💻 백준 1003: 피보나치 함수
백준 1003
dp(동적계획법) 문제이다.
recursive하게 구현된 피보나치 함수에서 0, 1이 프린트되는 횟수를 구해야 한다.
단계에서 보이는 짧은 문제 설명에서 보다시피 단순 재귀로 구하면 안된다.
재귀로 풀지말라는 의도가 선명..
N 에따른 0 출력수, 1 출력수를 보면
다음과 같다.
dp[i] = dp[i-2] + dp[i-1] 이다.
피보나치 함수와 똑같다..! 함수 호출이 진짜 기하급수적으로 늘어남을 알 수 있다.
코드
import java.util.Scanner;
public class Boj220311 {
public static void main(String[] args) {
/***************************************************************************/
/*
* boj 1003 피보나치 함수 - dp
*
* 18580 KB
* 244 ms
*
* */
int[] dp = new int[41];
dp[0] = 0;
dp[1] = 1;
for(int i = 2; i < dp.length; i++) {
dp[i] = dp[i-2] + dp[i-1];
}
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
int[] N = new int[T];
for(int i = 0; i < T; i++)
N[i] = sc.nextInt();
for(int i : N) {
if(i == 0)
System.out.println("1 0");
else {
System.out.println(dp[i-1]+" "+dp[i]);
}
}
}
}☕️ 잡담
벌써 내일이 코테인데 준비가 너무 안된 상태이다.
열심히 밀어넣고있다.
용돈 받아서 맛있는거 먹었다.
내일도 코테 끝나고 맛있는거..!
그리고 블로그 스킨이 마음에 들지 않는다..
TOC 뿅하고 만들고싶다
원해요 TOC 마니마니
댓글