KB IT’s Your Life 4기 - Java 알고리즘 13일차

b3344

package s2806_n_queen;

import java.util.Scanner;

public class Solution {
    static int answer;
    static int N;
    static int[] col;
    public static void main(String[] args) {
        Scanner in =new Scanner(System.in);
        int T = in.nextInt();
        for(int t=1; t<=T; ++t) {
            answer = 0;
            N=in.nextInt();
            col=new int[N+1];    // 0번 행을 제외하고 작업하기 위해 1을 더한다.각 행에 하나씩만 배치할 수 있기 때문에 1차원, col[i]번째방에 여왕을 배치할 열값을 저장한다.
            setQueens(1);        // 1행부터 시도
            System.out.println("#"+t+" "+answer);
        }
    }

    public static void setQueens(int rowNo){
 
        if(rowNo>N) {     // 시도하려는 rowNo행번호가 N보다 크면 말판끝까지 다 놓은 경우
            answer++;
            return;
        }
        for(int j=1; j<=N;j++){    // 해당 행의 1열부터 n열까지 퀸 놓는 시도
            col[rowNo]=j; 
            if(checking(rowNo)){ 
                setQueens(rowNo+1); 
            }
        }
    }

    // rowNo행에 퀸을 놓을수 있는지 1행부터 기존 rowNo-1행까지 rowNo행와 비교하며 체크
    public static boolean checking(int rowNo){
        for(int k=1; k<rowNo; k++){
            if(col[rowNo] == col[k] || Math.abs(col[rowNo]-col[k]) == rowNo-k){
                return false;
            }
        }
        return true;
    }
}

그래프

에지리스트
1. 가중치 없는 그래프
2. 가중치 있는 그래프
인접행렬
1. 가중치 없는 그래프
2. 가중치 있는 그래프
인접리스트
1. 가중치 없는 그래프
2. 가중치 있는 그래프

BFS - 너비우선탐색 (큐)

탐색 과정

BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기
큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입하기
스택 자료구조에 값이 없을 때까지 반복하기

DFS - 깊이우선탐색 (스택)

후입선출 특성

DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기
스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입하기
스택 자료구조에 값이 없을 때까지 반복하기

BFS vs DFS

어느 것이 유리할지는 문제를 많이 풀어봐아야 알 수 있다.

b11724

package b11724;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	static int n, m; // 노드 개수, 엣지 개수
	static ArrayList<Integer>[] A;
	static boolean[] visit;
	static int count;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		A = new ArrayList[n + 1];
		visit = new boolean[n + 1];

		for (int i = 1; i < n + 1; i++) {
			A[i] = new ArrayList<Integer>();
		}
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			A[s].add(e);
			A[e].add(s);
		}

		for(int i=1; i<= n; i ++) {
			if(!visit[i]) {
				count++;
				DFS(i);
			}
			
		}
		System.out.println(count);
	}

	private static void DFS(int i) {
		if(visit[i]) {
			return;
		}
		visit[i] = true;
		for(int j : A[i]) {
			if(visit[j] == false) {
				DFS(j);
			}
		}
		
	}
}

DFS와 BFS

package b1260;

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

public class Main {
	static int n, m, start; // 노드 개수, 엣지 개수, 시작점
	static ArrayList<Integer>[] A;
	static boolean[] visit;
	static int count;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		start = Integer.parseInt(st.nextToken());

		A = new ArrayList[n + 1];
		visit = new boolean[n + 1];

		for (int i = 1; i <= n ; i++) {
			A[i] = new ArrayList<Integer>();
		}
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			//양방향 그래프임으로 추가되는 코드이다.
			A[s].add(e);
			A[e].add(s);
		}
		
		for(int i =1; i<=n; i++) {
			Collections.sort(A[i]);
		}
		
		visit = new boolean[n+1];
		DFS(start);
		System.out.println();
		visit = new boolean[n+1];
		BFS(start);
	}

	private static void BFS(int start) {
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.add(start);
		visit[start] = true;

		while (!queue.isEmpty()) {
			int now_Node = queue.poll();
			System.out.print(now_Node + " ");
			for (int i : A[now_Node]) {
				if (!visit[i]) {
					visit[i] = true;
					queue.add(i);
				}
			}
		}
	}

	private static void DFS(int start) {
		if(visit[start]) {
			return;
		}
		visit[start] = true;
		System.out.print(start + " ");
		for(int j : A[start]) {
			if(visit[j] == false) {
				DFS(j);
			}
		}
	}
}