Coffee And Coding

- 분류 : DFS/BFS

- 문제 : https://www.acmicpc.net/problem/2606

- 문제 링크 : https://www.acmicpc.net/problem/1012

- 알고리즘 분류 : dfs/bfs

나는 DFS로 풀었다. 

• input = 배추의 위치 좌표가 주어진 배열이 주어진다.
• output = 필요한 배추흰지렁이의 개수
• DFS 사용 ⇒ 한 방향으로 갈 수 있는 곳까지 계속 탐색하고, 막다른 곳에 들어가면 거기에서 다시 안으로 쭉 들어간다. 막다른 곳에 도달할 때마다 배추지렁이의 개수를 늘리면 될듯하다.

다 풀고나서 계속 25%에서 틀려서 디버깅해보니까 continue를 써야하는 시점에 break를 써놔서 상하좌우를 전부 체크하지 않고 반복문을 빠져나갔기 때문이었다;;; 너무 황당한 실수...

import java.util.*;

 class CabbageField {
    int count; //배추 개수
    int cabbageMap[][]; //배추 위치 좌표
    boolean visited[][]; 
    int width;
    int height;
    int result;
    
    private int dx[] = {1,-1,0,0};
    private int dy[] = {0,0,1,-1};
   
    
    public CabbageField(int w, int h, int c) {
        this.width = w;
        this.height = h;
        this.count = c;
        this.cabbageMap = new int[w][h];
        this.visited = new boolean[w][h];
    }   
 
    
    public void dfs(int x, int y) {
        this.visited[x][y] = true;
        checkAdjacent(x,y);
    }
    
    private void checkAdjacent(int x, int y) {
        //상하좌우 4군데 체크
        for(int i = 0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx >= width || nx < 0 || ny >= height || ny < 0) {
                continue;
            }
            
            //재귀
            if(visited[nx][ny] == false && cabbageMap[nx][ny] == 1) {
                dfs(nx, ny);
            }
        }
        
    }
}




public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int total = sc.nextInt(); // case 개수
        CabbageField[] cabbageFields = new CabbageField[total];
        for(int i = 0; i<total; i++) {
            cabbageFields[i] = new CabbageField(sc.nextInt(), sc.nextInt(), sc.nextInt());
            
            //배추 좌표 입력
            for(int j = 0; j<cabbageFields[i].count; j++) {
                int x = sc.nextInt();
                int y = sc.nextInt();
                cabbageFields[i].cabbageMap[x][y] = 1;
            }
            
            for(int w = 0; w<cabbageFields[i].width; w++) {
                for(int h = 0; h<cabbageFields[i].height; h++) {
                    if(cabbageFields[i].cabbageMap[w][h] == 1 
                        && cabbageFields[i].visited[w][h] == false) {
                            cabbageFields[i].dfs(w,h);
                            cabbageFields[i].result++;
                        }
                }
            }
            
           
            System.out.println(cabbageFields[i].result);
            
        }
       
    }
}

추가적으로 찾아본 반례를 첨부하면 아래와 같다.

<배추밭 모양>

0000

0101

0111

1
4 3 5
1 1
3 1
1 2
2 2
3 2

answer : 1

- 알고리즘 분류 : DFS/BFS

나는 BFS를 이용해서 풀었다.

• 1번 컴퓨터가 바이러스에 걸렸을 때 감염된 컴퓨터 수를 구하라.
• DFS, BFS 둘다 사용 가능하지만, 일단 인접한 컴퓨터를 기준으로 먼저 탐색할 것이기 때문에 나는 BFS를 이용해서 풀었다.
• 1번 컴퓨터(root)를 시작으로 인접한 컴퓨터들부터 순차적으로 방문한다. 방문한 컴퓨터들은 연결되어있다는 뜻이므로 “감염된 컴퓨터의 수 = 방문한 컴퓨터의 수”가 된다.

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

class Computer {
    int num;//컴퓨터 번호
    boolean marked;//방문 여부
    LinkedList<Computer> adjacent; // 인접한 컴퓨터들

    Computer(int num) {
        this.num = num;
        this.marked = false;
        this.adjacent = new LinkedList<>();
    }
}

class Graph {
    Computer[] computers;
    int count; //바이러스에 감염된 컴퓨터 수

    Graph(int size) {
        this.computers = new Computer[size];
				// 컴퓨터 번호 매기기 
        for (int i = 0; i < size; i++) {
            computers[i] = new Computer(i + 1);
        }
        count = 0;
    }

    void addEdge(int i1, int i2) {
        Computer c1 = computers[i1 - 1];
        Computer c2 = computers[i2 - 1];
        if (!c1.adjacent.contains(c2)) {
            c1.adjacent.add(c2);
        }
        if (!c2.adjacent.contains(c1)) {
            c2.adjacent.add(c1);
        }
    }

    void bfs() {
        Queue<Computer> queue = new LinkedList<>();
        Computer root = computers[0]; // 1번 컴퓨터
        root.marked = true;
        queue.add(root);

        while (!queue.isEmpty()) {
						//queue에 들어있는 컴퓨터 꺼내서 방문
            Computer computer = queue.poll();
						// 인접한 컴퓨터가 있으면 큐에 담아준다
            for (Computer c : computer.adjacent) {
                if (c.marked == false) {
                    c.marked = true;
                    queue.add(c);
                }
            }
            visit(computer);
        }
    }

    void visit(Computer computer) {
				// 1번컴퓨터 제외
        if (computer.num != 1) {
            count += 1;
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int size = sc.nextInt();
        sc.nextLine();
        int edges = sc.nextInt();
        sc.nextLine();
        Graph g = new Graph(size);
        for (int i = 0; i < edges; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            g.addEdge(a, b);
            sc.nextLine();
        }

        g.bfs();
        System.out.print(g.count);
    }
}

- 문제 : https://www.acmicpc.net/problem/1260

- 분류 : DFS, BFS

- 풀이

• BFS (너비우선탐색)
  • 가까운 정점을 먼저 방문하는 구조이기 때문에, 가까운 정점을 저장해두고 순서대로 방문할 수 있도록 선입선출 구조인 Queue를 사용한다.

• DFS (깊이우선탐색) 
  • 재귀 또는 스택을 사용해서 자기자신을 호출하는 순환 알고리즘 형태를 띈다.
  • 일단 한방향으로 갈 수 있는 데까지 깊이있게 파고든 다음에 다음으로 이동하는 방식.

import java.util.*;


class Node {
    int number; //정점 번호는 1번부터 N번까지
    LinkedList<Node> adjacent;
    boolean visited;
    
    public Node(int number) {
        this.number = number;
        this.visited = false;
        this.adjacent = new LinkedList<Node>();
    }
    
}

class Graph {
    Node[] nodes;
    
    public Graph(int nodeCount) {
        this.nodes = new Node[nodeCount];
        for(int i = 0; i<nodeCount; i++) {
            this.nodes[i] = new Node(i+1);
        }
    }
    
     public void addEdge(int a, int b) {
        Node aNode = this.nodes[a-1];
        Node bNode = this.nodes[b-1];
        
        if(!aNode.adjacent.contains(bNode)) {
            aNode.adjacent.add(bNode);
            // 여러개일 경우 작은 정점 먼저 방문하도록 정렬
            Collections.sort(aNode.adjacent, new Comparator<Node>() {
               @Override
               public int compare(Node a, Node b) {
                   return a.number > b.number ? 1: -1;
               }
            });
            
        }
        
        if(!bNode.adjacent.contains(aNode)) {
            bNode.adjacent.add(aNode);
            // 여러개일 경우 작은 정점 먼저 방문하도록 정렬
            Collections.sort(bNode.adjacent, new Comparator<Node>() {
               @Override
               public int compare(Node a, Node b) {
                   return a.number > b.number ? 1: -1;
               }
            });
        }
        
        
    }
    
    public void dfs(int v) {
        Node vNode = this.nodes[v-1];
        System.out.print(vNode.number + " ");
        vNode.visited = true;
        
        for(Node node: vNode.adjacent) {
            if(node.visited == false) {
                dfs(node.number);
            }
        }
    }

    public void bfs(int v) {
        Queue<Node> q = new LinkedList<Node>();
        Node vNode = this.nodes[v-1];
        q.add(vNode);
        vNode.visited = true;
      
        while(!q.isEmpty()){
            Node toVisit = q.peek();
            q.poll();
            System.out.print(toVisit.number + " ");
            
            if(!toVisit.adjacent.isEmpty()) {
                for(Node node : toVisit.adjacent) {
                    if(!node.visited) {
                        q.add(node);
                        node.visited = true;
                    }
                }
            } 
        }
    }
    
    //방문기록 초기화
    public void clearVisited() {
        for(Node node : this.nodes) {
            node.visited = false;
        }
    }

    
}



public class Main
{
	public static void main(String[] args) {
	    Scanner sc = new Scanner(System.in);
	    
	    int nodeCount = sc.nextInt();
	    int edgeCount = sc.nextInt();
	    int v = sc.nextInt(); //startNode
	    
	    Graph g = new Graph(nodeCount);
	    
	    for(int i = 0; i<edgeCount; i++) {
	        int a = sc.nextInt();
	        int b = sc.nextInt();
	        
	        g.addEdge(a,b);
	    }
	    
	    g.dfs(v);
	   g.clearVisited();
	    System.out.println();
	    g.bfs(v);
	
	}
}

문제 : https://www.acmicpc.net/problem/18258

풀이

문제 자체는 쉽다. Queue에 대한 기본 개념만 있으면 쉽게 구현할 수 있다.

다만 계속 '시간초과'가 떠서 이를 해결하는 데 초점을 맞춰야 한다.

시간초과를 해결하기 위해서는 아래 방법들이 있다.

1. 시간이 오래 걸리는 Scanner나 System.out.print() 대신 => BufferedReader, BufferedWriter를 사용한다

• 입력된 데이터를 바로 전달되지 않고 buffer에 모았다가 한번에 전달하므로 데이터 처리 효율성을 높인다. 다만 입력받은 데이터를 전부 String타입으로 고정하기 때문에 다른 타입으로 변환하는 가공 작업이 필요하다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());

2. StringBuilder를 사용해서 output을 한번에 출력한다

코드 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Queue{
	
	StringBuilder sb = new StringBuilder();
	LinkedList<Integer> list = new LinkedList<Integer>();

	public void push(int x) {
		list.add(x);
	}
	
	public void pop() throws IOException {
		//가장 앞에 있는 정수를 빼고 그 수를 출력한다
		//만일 큐에 들어있는 정수가 없으면 -1 출력
		sb.append(list.isEmpty()? "-1": list.poll());
		sb.append("\n");
    }
	
	public void size() throws IOException {
		//큐에 들어있는 정수의 개수를 출력한다
		sb.append(list.size() + "\n");
		
	}
	
	public void empty() throws IOException {
		//큐가 비어있으면 1, 아니면 0 출력
		sb.append(list.isEmpty()?"1":"0");
		sb.append("\n");
	}
    
	public void front() throws IOException {
		//가장 앞에 있는 정수를 출력
		//만약 큐에 들어있는 정수가 없으면 -1 출력
		sb.append(list.isEmpty() ? "-1" : list.getFirst());
		sb.append("\n");
		
	}
	public void back() throws IOException {
		//가장 뒤에 있는 정수를 출력
		//만약 큐에 들어있는 정수가 없는 경우 -1 출력
		sb.append(list.isEmpty()? "-1" : list.getLast());
		sb.append("\n");
	
	}
    
    public void print() {
        System.out.print(sb);
    }
}
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		Queue q = new Queue();
		String command[] = new String[n];
		
		for(int i = 0; i<n; i++) {
			command[i] = br.readLine();
		}
		
		for(int i = 0; i<n; i++) {
			String tmp = command[i];
		
			switch(tmp) {
			case "front":
				q.front();
				break;
			case "pop":
				q.pop();
				break;
			case "size":
				q.size();
				break;
			case "empty":
				q.empty();
				break;
			case "back":
				q.back();
				break;
			default:
				String sx = tmp.substring(5);
				int x = Integer.parseInt(sx);
				q.push(x);
			}
		}
       
        q.print();
        br.close();
	}
}

참고자료

https://docs.oracle.com/javase/8/docs/api/java/io/BufferedReader.html

https://jhnyang.tistory.com/92

https://yeon-kr.tistory.com/152

https://www.acmicpc.net/problem/2164

- 분류 : Queue

아주 간단한 문제이다.

import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		
		Queue<Integer> q = new LinkedList();
		for(int i = 0; i<n ; i++) {
		    q.add(i+1);
		}
		
		while(q.size() > 1) {
		    q.remove();
		    int head = q.poll();
		    q.add(head);
		}
		
		System.out.println(q.poll());
		
	}
}

- 문제 :

https://www.acmicpc.net/problem/2630

- 분류 : 분할정복 알고리즘

기본적인 분할정복 알고리즘 문제이다.

첨에 2차원 배열을 어떻게 사분할로 쪼개지? 에서 조금 생각을 했는데 결국은 시작점을 상하좌우로 이동시켜서 생각하면 된다. 예를 들면 이렇다.

  //같은 색이 아니라면 1/4로 쪼갠다
int divide = n/2;

int [][] arr1 = new int[divide][divide];
int [][] arr2 = new int[divide][divide];
int [][] arr3 = new int[divide][divide];
int [][] arr4 = new int[divide][divide];


for(int i = 0; i<divide; i++) {
   for(int j = 0; j<divide; j++) {
       arr1[i][j] = arr[i][j];
       arr2[i][j] = arr[i+divide][j];
       arr3[i][j] = arr[i][j+divide];
       arr4[i][j] = arr[i+divide][j+divide];
   }
}

풀이

첨에 arr 배열 전체를 넘겨주는 방식으로 풀었는데 다른 사람들의 풀이를 보니 arr[][]을 static으로 두고, index만 넘겨서 푸는 방식으로 풀었길래 나도 그와 같은 방식으로 다시 풀어보았다. 

분할정복 알고리즘은 문제를 작은 방식으로 분할하여 해결하는 방식으로, 

이 문제는 "전체 종이 색깔이 같지 않으면 계속 쪼개는(divide)" 방식으로 해결한다. 전체 종이 색깔이 같아질 때 conquer된다.

첫번째 풀이

import java.util.*;

public class Main
{
    static int white = 0;
	static int blue = 0; 
	
	public static void main(String[] args) {
	    Scanner sc = new Scanner(System.in);
	  
	    int n = sc.nextInt();
	    int arr[][] = new int[n][n];
	    
	    for(int i = 0; i<n; i++) {
	        for(int j = 0; j<n; j++) {
	            arr[i][j] = sc.nextInt();
	        }
	        sc.nextLine();
	    }
	   
	    quad(arr);
	    
	    System.out.println(white);
	    System.out.println(blue);
	}
	
	 static void quad(int[][] arr) {
	    int n = arr[0].length;
	    
	    //전체가 같은 색이면 컬러 체크
	    if(n == 1 || isAllColorSame(arr)) {
	        checkColor(arr[0][0]);
	        return;
	    }
	   
        //같은 색이 아니라면 1/4로 쪼갠다
	    int divide = n/2;
	    
        int [][] arr1 = new int[divide][divide];
        int [][] arr2 = new int[divide][divide];
        int [][] arr3 = new int[divide][divide];
        int [][] arr4 = new int[divide][divide];
        
      
	    for(int i = 0; i<divide; i++) {
	       for(int j = 0; j<divide; j++) {
	           arr1[i][j] = arr[i][j];
	           arr2[i][j] = arr[i+divide][j];
	           arr3[i][j] = arr[i][j+divide];
	           arr4[i][j] = arr[i+divide][j+divide];
	       }
	    }
	    
	    quad(arr1);
	    quad(arr2);
	    quad(arr3);
	    quad(arr4);
	}
	
	
	 static boolean isAllColorSame(int[][] arr) {
	    int color = arr[0][0];
	    int n = arr[0].length;
	    
	    //전체가 같은 색인지 체크한다
	    for(int i = 0; i<n; i++) {
	        for(int j = 0; j<n; j++) {
	           if(color != arr[i][j]) {
	               return false;
	           }
	        }
	    }
	    return true;
	}
	
	static void checkColor(int color) {
       if(color == 0) {
            white++;
        } else {
            blue++;
        }
	}
}

두번째 풀이

import java.util.*;

public class Main
{
    static int white = 0;
	static int blue = 0; 
	static int arr[][];
	
	public static void main(String[] args) {
	    Scanner sc = new Scanner(System.in);
	  
	    int n = sc.nextInt();
	    arr = new int[n][n];
	    
	    for(int i = 0; i<n; i++) {
	        for(int j = 0; j<n; j++) {
	            arr[i][j] = sc.nextInt();
	        }
	        sc.nextLine();
	    }
	   
	    quad(n, 0, 0);
	    
	    System.out.println(white);
	    System.out.println(blue);
	}
	
	 static void quad(int n, int row, int column) {
	    
	    // 1. 전체가 같은 색이면 컬러 체크
	    if(n == 1 || isAllColorSame(n, row, column)) {
	        checkColor(arr[row][column]);
	        return;
	    }
	   
        // 2. 같은 색이 아니라면 1/4로 쪼갠다
	   int divide = n/2;
	    
       quad(divide, row, column);
       quad(divide, row+divide, column);
       quad(divide, row, column+divide);
       quad(divide, row+divide, column+divide);
	}
	
	
	//전체가 같은 색인지 체크
	 static boolean isAllColorSame(int n, int row, int column) {
	   int color = arr[row][column];
	   
	    for(int i = row; i<n+row; i++) {
	        for(int j = column; j<n+column; j++) {
	           if(color != arr[i][j]) {
	               return false;
	           }
	        }
	    }
	    return true;
	}
	
	static void checkColor(int color) {
       if(color == 0) {
            white++;
        } else {
            blue++;
        }
	}
}

딱 기본적인 stack을 활용한 문제이다.

• 문제 : https://www.acmicpc.net/problem/4949

<풀이>

• 괄호를 만나면 stack에 넣는다.
• 오른쪽 괄호의 경우 stack의 top에 있는 괄호와 짝을 이룰 경우 stack에 넣지 않고 stack에 들어있는 왼쪽 괄호를 pop한다.

• 최종적으로 stack이 비어있으면 yes를 출력한다.

아래는 java에서 제공하는 Stack을 사용한 풀이이다.

import java.util.Stack;
import java.util.Scanner;

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

        while (true) {
            String str = sc.nextLine();
            Stack<Character> stack = new Stack<>();

            if (str.equals("."))
                break;

            for (int i = 0; i < str.length(); i++) {
								// 괄호를 만났을때 
                if (str.charAt(i) == '[' || str.charAt(i) == ']' || str.charAt(i) == '(' || str.charAt(i) == ')') {
										// 넣으려는 괄호가 오른쪽 괄호일 경우는 stack에 왼쪽괄호가 top에 존재할때 stack에서 왼쪽 괄호를 빼낸다
                    if ((!stack.empty() && stack.peek() == '[' && str.charAt(i) == ']') || (!stack.empty() && stack.peek() == '(' && str.charAt(i) == ')')) {
                        stack.pop();
                    } else {
												// 괄호는 스택에 저장한다
                        stack.push(str.charAt(i));
                    }
                }
            }
            System.out.println(stack.isEmpty() ? "yes" : "no");
        }
    }
}

아래는 ArrayList를 이용해서 직접 Stack을 구현해서 푼 풀이이다.

import java.util.*;

/*
백준 4949번 균형잡힌 세상
분류 : stack
직접 스택 구현해서 풀기
* */


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

        while (true) {
            String str = scanner.nextLine();
            Stack stack = new Stack();
            if (str.equals("."))
                break;

            for (int i = 0; i < str.length(); i++) {
                if (str.charAt(i) == '[' || str.charAt(i) == ']' || str.charAt(i) == '(' || str.charAt(i) == ')') {
                    if ((!stack.isEmpty() && stack.peek() == '[' && str.charAt(i) == ']') || (!stack.isEmpty() && stack.peek() == '(' && str.charAt(i) == ')')) {
                        stack.pop();
                    } else {
                        stack.push(str.charAt(i));
                    }
                }
            }
            System.out.println(stack.isEmpty() ? "yes" : "no");
        }
    }

    private static class Stack {
        private List<Character> elements;
        private int elementSize;

        public Stack() {
            this.elements = new ArrayList<>();
            this.elementSize = 0;
        }

        public void push(char element) {
            elements.add(element);
            elementSize++;
        }

        public void pop() {
            if (isEmpty()) {
                throw new EmptyStackException();
            }

            elements.remove(elementSize - 1);
            elementSize--;
        }

        public char peek() {
            if (isEmpty()) {
                throw new EmptyStackException();
            }

            return elements.get(elementSize - 1);
        }

        public boolean isEmpty() {
            if (elementSize == 0) {
                return true;
            }
            return false;
        }


    }
}