알고리즘 공부 #9 : 그래프 탐색 기초

hyeon·2022년 2월 10일
0

알고리즘 시작

목록 보기
7/18

JAVA에서 QUEUE와 STACK

DFS : 깊이 우선 검색

-> STACK, 재귀를 이용하여 구현

STACK CLASS

1. 정의
Stack s=new Stack();

2. 메소드
push(E item) : 스택의 맨위에 객체 삽입
peek() : 스택의 맨위의 것 반환 (스택에서 pop하는것은 아님)
pop() : 스택의 맨위의 것 반환 후 제거
empty() : 스택이 비어있는지 boolean으로 리턴
search(Object o) : 전달된 객체가 존재하는 위치의 인덱스 반환 (인덱스 1부터 시작)

BFS : 넓이 우선 검색

-> QUEUE를 이용하여 구현

QUEUE CLASS

1. 정의
Queue q=new LinkedList();

2. 메소드
offer(E e) : 큐의 맨뒤에 주어진 객체를 넣음
add(E e) : 큐의 맨뒤에 주어진 객체를 넣음 성공여부에 따라 true나 exception 반환
peek() : 큐의 맨앞에 있는(제일 먼저 저장된) 요소 반환 비었을 시 null
poll() : 큐의 맨앞에 있는 요소 반환 후 제거
remove() : 큐의 맨앞에 있는 요소 제거
element() : 큐의 맨앞에 있는 요소 반환

DEQUE CLASS

1. 정의
양쪽으로 in out 할 수 있는 stack과 queue를 섞어놓은 자료구조
Deque deque =new ArrayDeque<>();

2. 메소드
addFirst(),push : 앞에 삽입, 용량 초과시 exception
offerFirst() : 앞에 삽입 용량 초과시 false

add, addLast()
offer, offerLast()

remove, removeFirst() : 앞에서 제거
poll, pollFirst() : 앞에서 제거 비어있으면 null
removeLast()
pollLast()

offerFirst

그래프를 저장하는 방법

인접행렬, 인접 리스트

백준 10845 : 큐

 import java.util.*;

public class Main {
	public static Scanner scan =new Scanner(System.in);
	public static StringBuilder sb=new StringBuilder();
	static int n,num,last;
	static String command;
	public static void main(String[] args) {
			Queue q=new LinkedList();
			n=scan.nextInt();
			for(int a=0;a<n;a++) {	
				command=scan.next();
				if(command.equals("push")) {
					num=scan.nextInt();
					q.offer(num);
					last=num;
				}
				if(command.equals("pop")) {
					boolean bol=q.isEmpty();
					if(bol==true) {
						sb.append("-1"+"\n");
					}
					else {
						sb.append(q.poll()+"\n");
					}
				}
				if(command.equals("size")) {
					sb.append(q.size()+"\n");
				}
				if(command.equals("empty")) {
					boolean bol=q.isEmpty();
					if(bol==true) {
						sb.append("1"+"\n");
					}
					else {
						sb.append("0"+"\n");
					}
				}
				if(command.equals("front")) {
					if(q.isEmpty()) {
						sb.append("-1"+"\n");
					}
					else {
						sb.append(q.peek()+"\n");
					}
					
					
				}
				if(command.equals("back")) {
					if(q.isEmpty()) {
						sb.append("-1"+"\n");					}

					else {
						sb.append(last+"\n");					}
					
					
				}

				}
					System.out.print(sb);
					
				}
		}

	

맨앞의 것을 출력하는것이 막혀서 블로그 찾아보았다. 큐는 신선한게 맨뒤이기 때문에 pop명령에서 last를 설정해주면서 갱신해주었다!
그리고 제출했으나 시간초과가 떴다. 시스템아웃에서 스트링 빌더로 바꿔서 해결했다!

백준 10866 : 덱(deque)

deque를 디큐라고 읽는줄 알았는데, dequeue=디큐 deque=덱이였다. ㅋㅋㅋㅋㅋ
자료구조 deque에 대해서 공부하고 메소드를 알아본 후에 간단하게 풀 수 있었다.

 import java.util.*;

public class Main {
	public static Scanner scan =new Scanner(System.in);
	public static StringBuilder sb=new StringBuilder();
	static int n,num,num2,last;
	static String command;
	public static void main(String[] args) {
			Deque dq=new ArrayDeque();
			n=scan.nextInt();
			for(int a=0;a<n;a++) {	
				command=scan.next();
				if(command.equals("push_front")) {
					num=scan.nextInt();
					dq.offerFirst(num);
				}
				if(command.equals("push_back")) {
					num2=scan.nextInt();
					dq.offerLast(num2);
				}
				if(command.equals("pop_front")) {
					boolean bol=dq.isEmpty();
					if(bol==true) {
						sb.append("-1"+"\n");
					}
					else {
						sb.append(dq.pollFirst()+"\n");
					}
				}
				if(command.equals("pop_back")) {
					boolean bol=dq.isEmpty();
					if(bol==true) {
						sb.append("-1"+"\n");
					}
					else {
						sb.append(dq.pollLast()+"\n");
					}
				}
				if(command.equals("size")) {
					sb.append(dq.size()+"\n");
				}
				if(command.equals("empty")) {
					boolean bol=dq.isEmpty();
					if(bol==true) {
						sb.append("1"+"\n");
					}
					else {
						sb.append("0"+"\n");
					}
				}
				if(command.equals("front")) {
					if(dq.isEmpty()) {
						sb.append("-1"+"\n");
					}
					else {
						sb.append(dq.peekFirst()+"\n");
					}
					
					
				}
				if(command.equals("back")) {
					if(dq.isEmpty()) {
						sb.append("-1"+"\n");					}

					else {
						sb.append(dq.peekLast()+"\n");					}
									
				}
				}
					System.out.print(sb);
					
				}
		}

백준 1260 : DFS와 BFS

  import java.util.*;

public class Main {
	public static Scanner scan =new Scanner(System.in);
	public static StringBuilder sb=new StringBuilder();
	public static StringBuilder sb2=new StringBuilder();

	static int n,m,v;
	static int[][] arr;

	static int[] visited;
	static int[] visited2;

	static String command;

	public static void main(String[] args) {
		
		n=scan.nextInt();
		m=scan.nextInt();
		v=scan.nextInt();
		arr=new int[n+1][n+1];
		visited=new int[n+1];
		visited2=new int[n+1];

		for(int i=0;i<m;i++) {
			int a=scan.nextInt();
			int b=scan.nextInt();
			arr[a][b]=1;
			arr[b][a]=1;
		}
		DFS(v);
		System.out.println(sb);
		BFS(v);
		System.out.println(sb2);

		}
	
	public static void DFS(int v) {
		Stack<Integer> stack =new Stack<>();

		stack.push(v);
		
		while(!stack.empty()) {
			int curr=stack.pop();	//노드를 pop
			
			if(visited[curr]==1)continue;		//방문한 노드이면 skip
			//그렇지 않으면
			visited[curr]=1;
			sb.append(curr+" ");
			for(int i=n;i>0;i--) {
				if(visited[i]==0&&arr[curr][i]==1) {//방문하지 않은 노드이고 간선이 존재하는 경우
					stack.push(i);
				}
			}
		}
		}
	public static void BFS(int v) {
		Queue<Integer> q=new LinkedList<>();
		
		visited2[v]=1;
		q.offer(v);
		
		while(q.isEmpty()==false) {
			int curr=q.poll();
			sb2.append(curr+" ");	//실제 방문
			
			for(int i=1;i<n+1;i++) {
				if(visited2[i]==0&&arr[curr][i]==1) {//방문하지 않은 노드이고 간선이 존재하는 경우
					visited2[i]=1;
					q.offer(i);
				}
			}
		}
	
	}
	
		}

첫번째 실수는 bfs와 dfs 함수 둘다 visited 배열을 같이 사용해서ㅠ
두번재 실수는 string builder도 같이사용해서
마지막으로 변수 잘못넣어서 어디가 잘못된지도 모르고 계속 엄한곳 고침 ㅠㅠ 시좁레전드..
이번에는 stack을 사용해서 dfs를 풀어봤지만 실제로는 재귀를 많이 사용하는 모양이다.

복습

import java.io.*;
import java.util.*;
public class Main {
	static int n,m,v,cnt=0;
	static String str;
	static Scanner scan=new Scanner(System.in);
	static StringBuilder sb=new StringBuilder();
	static ArrayList<ArrayList<Integer>> list= new ArrayList<>();
	static int[] ans;
	static boolean[] visited1,visited2;
    public static void main(String[] args)  {
    
    	n=scan.nextInt();//정점의 개수
    	m=scan.nextInt();  //간선의 개ㅜㅅ
    	v=scan.nextInt();//탐색을 시작할 정점의 번호
    	visited1=new boolean[n+1];		//n+1인 이유 : 원소들이 1부터 존재할 수 있기때문에 
    	visited2=new boolean[n+1];
    	
    	for(int i=0;i<n+1;i++) {		//마찬가지로 원소들이 1부터 존재 하니까 0은 빼고함
    		list.add(new ArrayList<Integer>());
    	}
    	for(int i=0;i<m;i++) {
    		int a=scan.nextInt();
    		int b=scan.nextInt();
    		list.get(a).add(b);
    		list.get(b).add(a);
    	}
    	for(int i=1;i<=n;i++) {
			Collections.sort(list.get(i));
		}

    	dfs(v,0);
    	System.out.println();

    	bfs(v);
    }
    static void dfs(int v, int cnt) {
    	System.out.print(v+" ");
    	if(cnt==n) {
    		 return;
    	}
    	visited1[v]=true;
    	for(int m:list.get(v)) {
    		if(visited1[m]==false) {
    			dfs(m,cnt+1); 
    		}
    	}
    	if(visited1[v]==false) {
    		visited1[v]=true;
    	}
    }
    static void bfs(int v) {
    	Queue<Integer> q=new LinkedList<>();
    	q.offer(v);
    	visited2[v]=true;
    	while(!q.isEmpty()) {
    		int temp=q.poll();
    		System.out.print(temp+" ");
    		for(int m:list.get(temp)) {
    			if(visited2[m]==false) {
    				visited2[m]=true;
    				q.offer(m);
    			}
    		}
    	}
    	
    	
    	}

    
  }

연결리스트로 구현해보았다.
visited와 list add할때 n+1 으로 해야하는지 이유를 몰랐고 오랫만에 하니까 dfs, bfs하는 방법이 잘 기억이 안나서 동영상도 한번 더 봤다.

백준 11724 : 연결요소의 개수

import java.util.*;

public class Main {
	public static Scanner scan =new Scanner(System.in);
	public static StringBuilder sb=new StringBuilder();
	public static StringBuilder sb2=new StringBuilder();

	static int n,m,v;
	static int[][] arr;
	static int cnt;
	static int[] visited;
	static int[] visited2;

	public static void main(String[] args) {
		
		n=scan.nextInt();
		m=scan.nextInt();
		arr=new int[n+1][n+1];
		visited=new int[n+1];

		for(int i=0;i<m;i++) {
			int a=scan.nextInt();
			int b=scan.nextInt();
			arr[a][b]=1;
			arr[b][a]=1;
		}
		for(int i=1;i<n+1;i++) {
			if(visited[i]==0) {
				dfs(i);
				cnt++;
			}
		}
		System.out.print(cnt);
	}
	
	public static void dfs(int v) {
		visited[v]=1;
		for(int i=1;i<n+1;i++) {
			if(visited[i]==0&&arr[v][i]==1) {
				dfs(i);
			}
		}
	}
	
	
	
		}

dfs로 끝까지 탐색한 후 아직 방문하지 않은 노드가 있을 때 그노드 부터 다시 dfs 시작해서 탐색 시작한 횟수를 세서 출력했다.

복습

연결요소가 뭔가했는데 그려보면 알수있다!
갑자기 boolean이 헷갈렸다. boolean은 초기값이 false이다.

                               import java.io.*;
import java.util.*;
public class Main {
	static int n,m,v,cnt=0;
	static String str;
	static Scanner scan=new Scanner(System.in);
	static StringBuilder sb=new StringBuilder();
	static ArrayList<ArrayList<Integer>> list= new ArrayList<>();
	static boolean[][] arr;
	static boolean[] visited1,visited2;
    public static void main(String[] args)  {
    //boolean의 초기값은 false 이다.
    	n=scan.nextInt();//정점의 개수
    	m=scan.nextInt();  //간선의 개수
    	arr=new boolean[n+1][n+1];
    	visited1=new boolean[n+1];		//n+1인 이유 : 원소들이 1부터 존재할 수 있기때문에 
    	
    	for(int i=0;i<m;i++) {
    		int a=scan.nextInt();
    		int b=scan.nextInt();
    		arr[a][b]=arr[b][a]=true;
    	}
    	
    	for(int i=1;i<n+1;i++) {
    		if(visited1[i]==false) {
    			dfs(i);
    			cnt++;
    		}
    	}
    	System.out.print(cnt);

    }
  
    static void dfs(int v) {
    	visited1[v]=true;
    	for(int j=1;j<n+1;j++) {
    		if(visited1[j]==false&&arr[v][j]==true) {//간선존재 방문x한곳일때
    			dfs(j);
    		}
    	}
    	return;
    }
  }
                               ```
                                                 
                                                 
profile
남기고 싶은 개발자입니다 :>

0개의 댓글