[백준] S1260

#https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

# 아이디어

막막하다.. 감도 안 잡힘.

 

일단 생각난 큰 틀

1. edge 입력받아서 vertex끼리 연결된 배열?같은거 만들기

2.

- DFS: 연결된 것 중에 가장 작은거 찾기 -> 작은 vertex로 이동 -> 재귀. 종료조건: cnt == vertex 수

- BFS: 연결된 것 중에 가장 작은 vertex 2개 찾아서 left, right 정하기 -> 큐에다가 왼쪽 전부 다, 오른쪽 전부 다 따로 출력???

 

처참한 코드...

package baekjoon;

import java.util.Scanner;

public class S1260 {

	public static void dfs(int start, int cnt) {

	}

	public static void bfs(int start) {

	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int vertex, edge, start;
		vertex = sc.nextInt();
		edge = sc.nextInt();
		start = sc.nextInt();

		int[] left = new int[vertex];
		int[] right = new int[vertex];
		for (int i = 0; i < edge; i++) {
			left[i] = sc.nextInt();
			right[i] = sc.nextInt();
		}
		
		// 간선 연결된 정보를 갖는 무언가 만들자
		

		int cnt = 0;
		dfs(start, cnt);
		System.out.println();
		cnt = 0;
		bfs(start);

	}

}

 

 

# 블로그 참조(ㄹㅈㄷ로 빠른 포기)

인접행렬을 그리자. 노드간에 간선이 연결된 좌표에 1저장.

노드의 번호가 1부터 시작하기 때문에 [N+1][N+1] 크기의 배열을 사용하면, 직관적으로 배열의 인덱스를 편하게 이용할 수 있다.

 

정답 코드

package baekjoon;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class S1260 {

	public static void dfs(int start, int[][] matrix, int[] visited) {
		visited[start] = 1;
		System.out.print(start + " ");

		int vertex = visited.length - 1;
		for (int i = 1; i <= vertex; i++) {
			if (matrix[start][i] == 1 && visited[i] == 0) {
				dfs(i, matrix, visited);
			}
		}

	}

	public static void bfs(int start, int[][] matrix, int[] visited) {		
		Queue<Integer> queue = new LinkedList<Integer>();
        queue.offer(start);
        visited[start] = 1;

        System.out.print(start + " ");

		int vertex = visited.length - 1;
        while(!queue.isEmpty()) {
            int n = queue.poll();

			// 노드 하나로 연결된 노드 먼저 다 체크 
            for(int i = 1; i <= vertex; i++) {
           		 // 연결된 노드인데 방문하지 않은 경우 
                if(matrix[n][i] == 1 && visited[i] == 0) {
                    visited[i] = 1;
                    System.out.print(i + " ");
                    queue.offer(i);
                }
            }
        } 
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int vertex, edge, start;
		vertex = sc.nextInt();
		edge = sc.nextInt();
		start = sc.nextInt();

		int[][] adjacencyMatrix = new int[vertex + 1][vertex + 1];
		int[] visited;

		int left, right;
		for (int i = 0; i < edge; i++) {
			left = sc.nextInt();
			right = sc.nextInt();
			adjacencyMatrix[left][right] = adjacencyMatrix[right][left] = 1;
		}

		visited = new int[vertex + 1];
		dfs(start, adjacencyMatrix, visited);
		System.out.println();

		visited = new int[vertex + 1];
		bfs(start, adjacencyMatrix, visited);

		sc.close();
		
	}

}

 

- DFS: 방문노드 visited 1로 바꿔주고, 노드 수만큼 for문을 반복하며 if 조건문을 통해 방문노드의 인접노드인지 판별 후 재귀.

- BFS: 맨처음 시작노드를 큐에 넣는다. 큐에 들어간 노드를 출력하고 for문으로 반복하며 출력한 노드와 인접한 노드를 방문하고 출력하고 큐에 저장한다. 이를 큐가 빌 때까지 반복함.

 

최종 수정 코드

package baekjoon;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class S1260 {

	public static void dfs(int start, int[][] matrix, int[] visited) {
		visited[start] = 1;
		System.out.print(start + " ");

		int vertex = visited.length - 1;
		for (int i = 1; i <= vertex; i++) {
			if (matrix[start][i] == 1 && visited[i] == 0) {
				dfs(i, matrix, visited);
			}
		}

	}

	public static void bfs(int start, int[][] matrix, int[] visited) {
		Queue<Integer> queue = new LinkedList<Integer>();

		visited[start] = 1;
		queue.offer(start);

		int vertex = visited.length - 1;
		while (!queue.isEmpty()) {
			int n = queue.poll();
			System.out.print(n + " ");

			for (int i = 1; i <= vertex; i++) {
				if (matrix[n][i] == 1 && visited[i] == 0) {
					visited[i] = 1;
					queue.offer(i);
				}
			}
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int vertex, edge, start;
		vertex = sc.nextInt();
		edge = sc.nextInt();
		start = sc.nextInt();

		int[][] adjacencyMatrix = new int[vertex + 1][vertex + 1];
		int[] visited;

		int left, right;
		for (int i = 0; i < edge; i++) {
			left = sc.nextInt();
			right = sc.nextInt();
			adjacencyMatrix[left][right] = adjacencyMatrix[right][left] = 1;
		}

		visited = new int[vertex + 1];
		dfs(start, adjacencyMatrix, visited);
		System.out.println();

		visited = new int[vertex + 1];
		bfs(start, adjacencyMatrix, visited);

		sc.close();

	}

}

 

 

💯💯💯

DFS, BFS 감도 안 잡히네;;;

백준 문제 많이 풀어봐야 할 듯...