BangBang's Devlogs

www.acmicpc.net/problem/1766

문제

* 위상 정렬의 대표적인 문제이다.
(줄 세우기 문제에 약간 심화문제 우선순위 큐 사용)
yubh1017.tistory.com/manage/newpost/83?type=post&returnURL=https%3A%2F%2Fyubh1017.tistory.com%2F83

Queue를 이용한 위상정렬로 구현하였다. 

문제를 풀기전 간단하게 위상정렬에 대한 설명을 하자면

1. 위상 정렬은 그래프 정렬을 말한다.

2. 위상 정렬이 가능하려면 DAG(Directed Acyclic Graph, 방향성이 있으며 사이클이 없는 그래프) 여야 한다.

• 두 노드 A,B 사이에 A->B 같은 관계가 성립되어야 하며
• A->B 관계가 성립하면 B->A나 B->C->A와 같이 사이클이 생겨서는 안된다.

3. 자기 자신을 가리키는 간선의 갯수인 indegree 배열을 이용하여 구현할 수 있다.

4. 위상 정렬 과정

4.1) 위상 정렬을 위해 두개의 Queue를 만들어준다. 
q : indegree 값이 0인 노드들을 담기위한 Queue 
result: q에서 꺼내져 결과로 출력하기 위해 담는 결과 Queue

4.2) 처음 indegree 간선의 갯수가 0인 index를 q에 넣어준다.

4.3) q가 empty일 때까지 while문을 돈다.
q.poll()한 노드를 result에 넣어준다.(result.offer(노드))
그리고 해당 노드에 연결된 노드의 간선의 갯수들을 지워주면서 간선의 갯수가 0이 되면 q에 넣어준다.

4.4) result에 담긴 node가 위상정렬 순서가 된다.

* 자세한 개념은 References에서 참고할 수 있으며 코드를 보고 이해 바랍니다.

References

위상 정렬 개념 : bcp0109.tistory.com/entry/%EC%9C%84%EC%83%81%EC%A0%95%EB%A0%AC-Topological-Sort-Java?category=848939

해결 방안

문제 수 n이 정점(v)의 갯수가 되고 m은 간선(e)의 갯수가 될 것이다. 

따라서 이차원 ArrayList를 이용하여 단방향성 그래프를 생성해주고 가리킴을 받는 간선의 indegree[index]의 간선의 갯수를 증가해준다.

그리고 위상 정렬을 해준다.

여기서 3번 조건인 '가능하면 쉬운문제부터 풀어야한다.' 를 만족하기 위해 기존의 q에서 pq(우선순위큐)로 바꿔서 문제를 풀어준다. (문제는 난이도 순서로 출제되어 있기 때문에)

코드

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

// 문제집
// 우선순위 큐를 이용한 위상정렬2
// 가능하면 쉬운 문제를 먼저 풀어야 하며 난이도 순서로 문제가 출제되어있다. => 우선순위 큐를 사용
public class Main {

	static int n; // 문제 수
	static int m; // 조건(간선)
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		n = Integer.parseInt(str.split(" ")[0]);
		m = Integer.parseInt(str.split(" ")[1]);
		
		int[] indegree = new int[n+1];
		ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
		for(int i=0; i<n+1; i++) {
			graph.add(new ArrayList<Integer>());
		}
		
		int a,b;
		for(int i=0; i<m; i++) {
			str = br.readLine();
			a = Integer.parseInt(str.split(" ")[0]);
			b = Integer.parseInt(str.split(" ")[1]);
			
			graph.get(a).add(b);
			indegree[b]++;
		}
		// === 입력 끝
		
		topologicalSort(indegree, graph);
	}
	
	static void topologicalSort(int[] indegree, ArrayList<ArrayList<Integer>> graph) {
		PriorityQueue<Integer> pq = new PriorityQueue<>(); // 간선의 갯수가 0인것
		Queue<Integer> result = new LinkedList<>();
		
		for(int i=1; i<n+1; i++) {
			if(indegree[i]==0)
				pq.offer(i);
		}
		
		int node;
		while(!pq.isEmpty()) {
			node = pq.poll();
			result.offer(node);
			
			for(int i: graph.get(node)) {
				indegree[i]--;
				
				if(indegree[i]==0)
					pq.offer(i);
			}
		}
		
		while(!result.isEmpty()) {
			System.out.print(result.poll() + " ");
		}
	}

}

www.acmicpc.net/problem/2252

문제

* 위상 정렬의 대표적인 문제이다.

Queue를 이용한 위상정렬로 구현하였다. 

문제를 풀기전 간단하게 위상정렬에 대한 설명을 하자면

1. 위상 정렬은 그래프 정렬을 말한다.

2. 위상 정렬이 가능하려면 DAG(Directed Acyclic Graph, 방향성이 있으며 사이클이 없는 그래프) 여야 한다.

• 두 노드 A,B 사이에 A->B 같은 관계가 성립되어야 하며
• A->B 관계가 성립하면 B->A나 B->C->A와 같이 사이클이 생겨서는 안된다.

3. 자기 자신을 가리키는 간선의 갯수인 indegree 배열을 이용하여 구현할 수 있다.

4. 위상 정렬 과정

4.1) 위상 정렬을 위해 두개의 Queue를 만들어준다.
q : indegree 값이 0인 노드들을 담기위한 Queue
result: q에서 꺼내져 결과로 출력하기 위해 담는 결과 Queue

4.2) 처음 indegree 간선의 갯수가 0인 index를 q에 넣어준다.

4.3) q가 empty일 때까지 while문을 돈다.
q.poll()한 노드를 result에 넣어준다.(result.offer(노드))
그리고 해당 노드에 연결된 노드의 간선의 갯수들을 지워주면서 간선의 갯수가 0이 되면 q에 넣어준다.

4.4) result에 담긴 node가 위상정렬 순서가 된다.

* 자세한 개념은 References에서 참고할 수 있으며 코드를 보고 이해 바랍니다.

References

위상 정렬 개념 : bcp0109.tistory.com/entry/%EC%9C%84%EC%83%81%EC%A0%95%EB%A0%AC-Topological-Sort-Java?category=848939

해결 방안

사람 수 N이 정점(v)의 갯수가 되고 M은 간선(e)의 갯수가 될 것이다. 

따라서 이차원 ArrayList를 이용하여 단방향성 그래프를 생성해주고 가리킴을 받는 간선의 indegree[index]의 간선의 갯수를 증가해준다.

그리고 위상 정렬을 해준다.

코드

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

// 줄 세우기
// 위상정렬 문제
// 단방향
public class Main {

	static int N;
	static int M;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		N = Integer.parseInt(str.split(" ")[0]); // 정점 갯수(사람 수)
		M = Integer.parseInt(str.split(" ")[1]); // 간선 갯수
		
		// 자기한테 온 간선의 갯수
		int[] indegree = new int[N+1];
		ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
		for(int i=0; i<N+1; i++) {
			graph.add(new ArrayList<Integer>());
		}
		
		int a,b;
		for(int i=0; i<M; i++) {
			str = br.readLine();
			a = Integer.parseInt(str.split(" ")[0]);
			b = Integer.parseInt(str.split(" ")[1]);
			
			graph.get(a).add(b);
			indegree[b]++;
		}
		// ==== 입력 끝
		
		topologicalSort(indegree, graph);
		
	}
	
	static void topologicalSort(int[] indegree, ArrayList<ArrayList<Integer>> graph) {
		Queue<Integer> q = new LinkedList<>(); // 간선의 갯수가 0인 정점이 들어갈 곳
		Queue<Integer> result = new LinkedList<>(); // 순서에 대한 결과가 들어갈 곳
		
		for(int i=1; i<=N; i++) {
			if(indegree[i]==0)
				q.offer(i);
		}
		
		int current;
		while(!q.isEmpty()) {
			current = q.poll();
			result.offer(current);
			
			for(int i : graph.get(current)) {
				indegree[i]--;
				
				if(indegree[i]==0)
					q.offer(i);
			}
		}
		
		while(!result.isEmpty()) {
			System.out.print(result.poll() + " ");
		}
	}

}

www.acmicpc.net/problem/7576

문제

해결 방안

BFS를 기본으로하여 구현하였다. 

코드

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

// 토마토
// 며칠이 지나면 토마토가 다 익게되는지 최소 일수
public class Main {

	static int M; // 가로 (2~1000)
	static int N; // 세로
	static int[][] map; // NxM (1(익음),0(안익음),-1(없음))
	static boolean[][] visited;
	static Queue<int[]> loc = new LinkedList<int[]>(); // 익은 것들 위치
	static int[] dx = {0, 1, 0, -1}; // 북, 동, 남, 서
	static int[] dy = {-1, 0, 1, 0}; // 북, 동, 남, 서
	static int totalTomatoCnt = 0; // 총 토마토 갯수
	static int tomatoCnt = 0; // 익은 토마토 cnt
	static int result = 0; // 토마토가 모두 익는 최소 날짜
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		M = Integer.parseInt(str.split(" ")[0]);
		N = Integer.parseInt(str.split(" ")[1]);
		
		map = new int[N][M];
		visited = new boolean[N][M];
		
		StringTokenizer st;
		for(int i=0; i<N; i++) {
			str = br.readLine();
			st = new StringTokenizer(str);
			
			for(int j=0; j<M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				// 토마토 갯수
				if(map[i][j]==1 || map[i][j] == 0) {
					
					totalTomatoCnt++;
					// 익은 토마토를 
					if(map[i][j]==1) {
						tomatoCnt++;						
						loc.offer(new int[]{i,j});
						visited[i][j] = true;
					}
					
				}
			}
		}
		
		bfs();
		
		System.out.println(result);
	}
	
	static void bfs() {
		if(tomatoCnt == totalTomatoCnt) {
			return;
		}
		
		Queue<int[]> depthLoc = new LinkedList<>();
		int[] current = new int[2];
		int nx, ny;
		
		while(!loc.isEmpty()) {
			if(tomatoCnt == totalTomatoCnt) {
				break;
			}
			
			while(!loc.isEmpty()) {
				current = loc.poll();
				depthLoc.offer(current);
			}
			
			while(!depthLoc.isEmpty()) {
				current = depthLoc.poll();
				
				for(int i=0; i<4; i++) {
					nx = current[1] + dx[i];
					ny = current[0] + dy[i];
					if(nx<0 || nx>=M || ny<0 || ny>=N) {
						continue;
					}
					else {
						if(!visited[ny][nx] && map[ny][nx]==0) {
							visited[ny][nx] = true;
							map[ny][nx]=1;
							loc.offer(new int[] {ny, nx});
							tomatoCnt++;
						}
					}
				}
				
			}
			result++;
			
		}
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(map[i][j]==0) {
					result = -1;
				}
			}
		}
		
	}

}

programmers.co.kr/learn/courses/30/lessons/12973?language=java

Stack 자료구조를 활용하여 구현하였습니다.

해결 방안

문자열의 문자들을 Stack에 넣어주면서 stack.peek()이 넣으려는 문자와 같으면 pop()해주고 아니면 push()해준다.

다 끝난 후 stack이 비어있으면 성공적으로 수행하였으므로 1, 비어있지 않으면 0을 반환해준다.

코드

import java.util.*;
class Solution
{
    public int solution(String s)
    {
        int answer = 0;
        
        char[] sChar = s.toCharArray();
        Stack<Character> stack = new Stack<>();
        
        for(int i=0; i<s.length(); i++){
            if(!stack.isEmpty() && stack.peek()==sChar[i]){
                stack.pop();
            }
            else{
                stack.push(sChar[i]);    
            }
        }
        
        if(stack.isEmpty())
            answer = 1;
        else
            answer = 0;

        return answer;
    }
}

www.acmicpc.net/problem/15970

문제

각 점에서 색깔이 같은 가장 가까운 점과 연결한 화살표들의 길이 합을 구하는 문제이다.

해결 방안

색깔마다 점의 배열을 만들어서 정렬을 한 뒤 각 점에서 가장 가까운 선(왼쪽 혹은 오른쪽)을 구해서 더해주면 되겠다고 생각하였다.

HashMap을 사용하여 점들의 색깔마다 ArrayList(점의 위치 배열)를 만들어주었다.

그 후 색깔마다 점의 위치 배열을 정렬해주고 각 점에서 가장 가까운 점까지의 화살표 길이를 더해주었다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N; // 점들의 갯수
		int x; // 점의 좌표
		int y; // 점의 색깔
		String str = br.readLine();
		N = Integer.parseInt(str);
		
		Map<Integer, ArrayList<Integer>> map = new HashMap<>();
		for(int i=0; i<N; i++) {
			str = br.readLine();
			x = Integer.parseInt(str.split(" ")[0]);
			y = Integer.parseInt(str.split(" ")[1]);
			
			// 색깔별 점의 좌표
			if(map.containsKey(y)) {
				map.get(y).add(x);
			}
			else {
				map.put(y, new ArrayList<Integer>());
				map.get(y).add(x);
			}
		}
		
		int sum = 0;
		Set<Integer> keys = map.keySet();
		// 1~N
		for(int key: keys) {
			ArrayList<Integer> arr = map.get(key);
			Collections.sort(arr);
			
			int distance = 0;
			int l=0;
			int r=0;
			for(int i=0; i<arr.size(); i++) {
				if(i==0) {
					distance = arr.get(i+1)-arr.get(i);
				}
				else if(i==arr.size()-1) {
					distance = arr.get(i)-arr.get(i-1);
				}
				else {
					l = arr.get(i)-arr.get(i-1);
					r = arr.get(i+1)-arr.get(i);
					distance = Math.min(l, r);
				}
				sum += distance;
			}
		}
		System.out.println(sum);
	}

}

www.acmicpc.net/problem/17609

문제

회문인지, 유사 회문(한글자만 삭제하면 회문이 되는 경우)인지, 일반 문자열인지 확인하는 문제이다.

해결 방안

주어진 단어의 첫 부분은 증가시키고 끝 부분은 감소시키면서 비교해온다.
이 때 단어의 변화되는 첫 부분 문자와 끝 부분의 문자가 가운데에 올 때가지 같으면 회문(0)이다.

그렇지 않은 경우 첫 부분을 하나 증가시키거나 끝 부분을 하나 감소시켜서 한 글자를 삭제 시켜서 확인을 해보고 둘 중  하나의 경우라도 회문이면 유사회문(1)이고 둘다 안되면 일반 문자열(2)인 경우이다.

이를 코드로 나타내면 아래와 같다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;

// 회문
// 회문:0 유사회문:1 그외:2
public class Main {

	static int T;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		T = Integer.parseInt(br.readLine());
		
		String word = "";
		int result = 0;
		
		for(int i=0; i<T; i++) {
			
			word = br.readLine();
			result = palindrome(word);
			
			System.out.println(result);
		}

	}
	
	public static int palindrome(String word) {
		int result = 0;
		int left = 0, right = word.length()-1;
		
		while(left<=right) {
			
			if(word.charAt(left) == word.charAt(right)) {
				left++;
				right--;
			}
			else {
				int l = left;
				int r = right;
				
				l++;
				while(l<=r) {
					if(word.charAt(l) == word.charAt(r)) {
						l++;
						r--;
					}
					else {
						result++;
						break;
					}
				}
				
				l = left;
				r = right;
				
				r--;
				while(l<=r){
					if(word.charAt(l) == word.charAt(r)) {
						l++;
						r--;
					}
					else {
						result++;
						break;
					}
				}
				
				return result;
			}
		}
		
		return result;
	}

}

www.acmicpc.net/problem/17608

문제

해결 방안

뒤에서부터 확인을 하므로 Stack을 이용하여 구현하였다.

기준 막대기높이(standard)보다 비교하는 막대기높이(current)가 크면 갯수를 하나씩 늘려주고 standard를 current로 바꿔준다.

코드

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

// 막대기
public class Main {

	public static void main(String[] args) throws IOException {

		Stack<Integer> stack = new Stack<>();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		int n = Integer.parseInt(str);
		
		int h=0;
		for(int i=0; i<n; i++) {
			str = br.readLine();
			h = Integer.parseInt(str);
			stack.push(h);
		}
		// ==== 입력 끝
		
		int standard = stack.pop();
		int cnt = 1;
		int current = 0;
		while(!stack.isEmpty()) {
			current = stack.pop();
			if(current > standard) {
				standard = current;
				cnt++;
			}
		}
		
		System.out.println(cnt);
	}

}

www.acmicpc.net/problem/17616

문제

그래프를 만들어야 되는 문제라고 생각은 했으나 어떻게 문제를 접근해야할지 몰라서 다른사람 풀이 참고함

참고 블로그: home-body.tistory.com/646

해결 방안

가능한 가장 높은 등수 U와 가능한 가장 낮은 등수 V를 구하는 문제이다.

크게 보자면 단방향 그래프로 lower_graph와 higher_graph 두개를 이용해서 U와 V를 구해주었다.

lower_graph는 x에서 시작하는 x보다 뒤의 순서들이 나열될 것이다. 따라서 인접 노드의 갯수를 구한뒤 +1을 해주면 가능한 가장 높은 등수 U가 된다.

higher_graph는 x에서 시작하는 x보다 앞의 순서들이 나열될 것이다. 따라서 n에서 인접노드의 갯수를 빼면 가능한 가장 낮은 등수 V가 될것이다. 

코드

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

//한국정보올림피아드
//KOI 2019 2차대회 초등부
//등수 찾기
public class Main {

	static int n, m, x;
	static int u, v; // u가 가능한 가장 높은 등수, v가 가능한 가장 낮은 등수
	
	static ArrayList<ArrayList<Integer>> higer_graph;
	static ArrayList<ArrayList<Integer>> lower_graph;
	static boolean[] visited;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String str = br.readLine();
		n = Integer.parseInt(str.split(" ")[0]);
		m = Integer.parseInt(str.split(" ")[1]);
		x = Integer.parseInt(str.split(" ")[2]);
		
		higer_graph = new ArrayList<>();
		lower_graph = new ArrayList<>();
		
		
		for(int i=0; i<n+1; i++) {
			higer_graph.add(new ArrayList<Integer>());
			lower_graph.add(new ArrayList<Integer>());
		}
		
		// 단방향 그래프
		int a,b;
		for(int i=0; i<m; i++) {
			str = br.readLine();
			a = Integer.parseInt(str.split(" ")[0]);
			b = Integer.parseInt(str.split(" ")[1]);
			
			higer_graph.get(a).add(b);
			lower_graph.get(b).add(a);
		}
		
		System.out.println((1+bfs(x, lower_graph)) + " " + (n-bfs(x, higer_graph)));
		
	}
	
	public static int bfs(int start, ArrayList<ArrayList<Integer>> graph) {
		visited = new boolean[n+1];
		
		Queue<Integer> q = new LinkedList<>();
		q.offer(start);
		visited[start] = true;
		int result = 0;
		
		int current;
		int y; // 인접노드
		while(!q.isEmpty()) {
			current = q.poll();
			//System.out.print(current + " ");
			
			for(int i=0; i<graph.get(current).size(); i++) {
				y = graph.get(current).get(i);
				
				if(!visited[y]) {
					q.offer(y);
					visited[y] = true;
					result++;
				}
			}
		}
		//System.out.println();
		return result;
	}

}