My Dev Blog

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

public class BfsIceCream {
	
	// 결과적으로 이 코드는 아이스크림 재료를 부을 수 있는 칸 0이 나오면 카운트를 증가하고,
	// 그곳의 상하좌우, 그 상하좌우의 또 상하좌우들을 전부 1로 만들어줘서 0으로부터 아이스크림이 생성될 수 있는 모든 곳을 1로 바꿔주는 코드이다.
	// 즉 0이 있다면 1로 만들고 카운트 증가 & 거기서부터 아이스크림이 만들어질 수 있는 모든 공간 1로 변경
	// 더이상 1로 바꿀 것이 없다면 다음 칸에서 다시 0인지 체크
	
	static int n = 0;
	static int m = 0;
	static String str = "";
	static int[][] arr = new int[1000][1000];
	public static int[] moveRow = {-1, 1, 0, 0};
	public static int[] moveCol = {0, 0, -1, 1};
	
	public static boolean bfs(int a, int b) {
		
		Queue<Point> q = new LinkedList<>();
		
		if (arr[a][b] == 0) { // 아이스크림 재료를 부을 수 있는 칸이라면
			
			q.offer(new Point(a,b));
			
			arr[a][b] = 1; // 아이스크림 재료 붓기
			
			while (!q.isEmpty()) {
				
				Point p = q.poll();
				
				int row = p.x;
				int col = p.y;
				
				for (int z = 0; z < 4; z++) { // 아이스크림 재료를 부은 칸의 상, 하, 좌, 우 확인하며 재료를 부을 수 있다면 같이 얼려서 아이스크림 덩어리 키우기
					int nextRow = row + moveRow[z];
					int nextCol = col + moveCol[z];
					
					// 4회 반복으로 인해 nextRow, nextCol은 아이스크림 재료를 부은 칸의 상, 하, 좌, 우 좌표가 될 것
					
					if (nextRow < 0 || nextRow > n - 1 || nextCol < 0 || nextCol > m - 1) { // 범위를 벗어난다면 continue
						continue;
					}
					
					if (arr[nextRow][nextCol] == 0) { // nextRow, nextCol이 재료를 부을 수 있는 칸이라면
						q.offer(new Point(nextRow,nextCol)); // nextRow, nextCol 기준 상, 하, 좌, 우 좌표 또한 같이 얼릴 수 있는 칸인지 확인을 위해 큐에 담기
						
						arr[nextRow][nextCol] = 1; // 재료 붓기
					}
				}
			}
			
			return true; // 아이스크림 재료를 부을 수 있는 칸이었으므로 true 리턴하여 result 값 1 증가되도록 하기
		}
		
		return false; // 아이스크림 재료를 부을 수 없는 칸이므로 false 리턴
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scan = new Scanner(System.in);
		
		System.out.print("행을 입력하세요 : ");
		
		n = scan.nextInt(); // 정수 입력 후 엔터를 치면 // 여기에 정수
		
//		scan.nextLine(); // 버퍼 비워주기 // 여기에 위에서 입력한 엔터
		
		System.out.print("열을 입력하세요 : ");
		
		m = scan.nextInt(); // 여기에 정수
		
		scan.nextLine(); // 버퍼 비워주기 // 위에서 입력받은 엔터들 이쪽으로
		
		System.out.println(n + "행 " + m + "열의 아이스크림 틀에서 아이스크림을 만듭니다. 빈 공간은 0 막힌 공간은 1로 입력해주세요 : ");
		
		for (int i = 0; i < n; i++) {
			System.out.print((i+1) + "번째 줄 입력 : ");
			str = scan.nextLine();
			for (int j = 0; j < m; j++) {
				arr[i][j] = str.charAt(j) - '0';
			}
		}
		
		scan.close(); // 입력 그만 받도록
		
		int result = 0;
		
		for (int k = 0; k < n; k++) {
			for (int z = 0; z < m; z++) {
				if (bfs(k, z)) {
					result += 1; // 결과적으로 이 result 카운트는 총 n x m 횟수 중 true일 경우에만 증가한다.
				}
			}
		}
		
		System.out.print("아이스크림 갯수 : " + result);
	}
}

BFS 알고리즘 문제 풀이 Java

import java.util.Scanner;

public class DfsIceCream {
	
	// 결과적으로 이 코드는 아이스크림 재료를 부을 수 있는 칸 0이 나오면 카운트를 증가하고,
	// 그곳의 상하좌우, 그 상하좌우의 또 상하좌우들을 전부 1로 만들어줘서 0으로부터 아이스크림이 생성될 수 있는 모든 곳을 1로 바꿔주는 코드이다.
	// 즉 0이 있다면 1로 만들고 카운트 증가 & 거기서부터 아이스크림이 만들어질 수 있는 모든 공간 1로 변경
	// 더이상 1로 바꿀 것이 없다면 다음 칸에서 다시 0인지 체크
	
	static int n = 0;
	static int m = 0;
	static String str = "";
	static int[][] arr = new int[1000][1000];
	
	public static boolean dfs(int a, int b) {
		
		if (a < 0 || a > n - 1 || b < 0 || b > m - 1) { // 범위 벗어나는지 확인
			return false;
		}
		
		if (arr[a][b] == 0) { // 아이스크림을 만들 수 있는 공간이라면
			arr[a][b] = 1; // 아이스크림을 붓기
			dfs(a, b + 1); // 상 칸도 만들 수 있는 공간이라면 아이스크림 붓기위해 dfs함수 실행 // 여기서 또 0이 나오면 아이스크림 붓고 상,하,좌,우 체크하여 dfs함수 실행 반복 또 반복
			dfs(a, b - 1); // 하 칸도 만들 수 있는 공간이라면 아이스크림 붓기위해 dfs함수 실행
			dfs(a - 1, b); // 좌 칸도 만들 수 있는 공간이라면 아이스크림 붓기위해 dfs함수 실행
			dfs(a + 1, b); // 우 칸도 만들 수 있는 공간이라면 아이스크림 붓기위해 dfs함수 실행
			return true; // 아이스크림을 만들었다면 카운트 증가를 위해 true 반환
		}
		
		return false;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scan = new Scanner(System.in);
		
		System.out.print("행을 입력하세요 : ");
		
		n = scan.nextInt(); // 정수 입력 후 엔터를 치면 // 여기에 정수
		
//		scan.nextLine(); // 버퍼 비워주기 // 여기에 위에서 입력한 엔터
		
		System.out.print("열을 입력하세요 : ");
		
		m = scan.nextInt(); // 여기에 정수
		
		scan.nextLine(); // 버퍼 비워주기 // 위에서 입력받은 엔터들 이쪽으로
		
		System.out.println(n + "행 " + m + "열의 아이스크림 틀에서 아이스크림을 만듭니다. 빈 공간은 0 막힌 공간은 1로 입력해주세요 : ");
		
		for (int i = 0; i < n; i++) {
			System.out.print((i+1) + "번째 줄 입력 : ");
			str = scan.nextLine();
			for (int j = 0; j < m; j++) {
				arr[i][j] = str.charAt(j) - '0';
			}
		}
		
		scan.close(); // 입력 그만 받도록
		
		int result = 0;
		
		for (int k = 0; k < n; k++) {
			for (int z = 0; z < m; z++) {
				if (dfs(k, z)) {
					result += 1; // 결과적으로 이 result 카운트는 총 n x m 횟수 중 true일 경우에만 증가한다.
				}
			}
		}
		
		System.out.print("아이스크림 갯수 : " + result);
	}
}

DFS 알고리즘 문제 풀이 Java

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class BreadthFirstSearch {
	
	// BFS
	// [BFS 알고리즘] 큐 사용 // peek() : Queue에 맨 앞에 있는 데이터를 가져온다 (Queue에서 꺼내진 않음) // poll() : Queue에 맨 앞에 있는 데이터 꺼낸다 // offer() : Stack에 데이터를 삽입
	// (6)--(2)--(1)--(3)--(5)
	//       |  /           |  \
	//      (8)            (4)--(7)
	
	public static boolean[] visited = new boolean[9];
	public static ArrayList<ArrayList<Integer>> graph = new ArrayList<>(); // 2차원 배열 또는 리스트 활용하자
//	public static int[][] arr = {{}, {2,3,8}, {1,6,8}, {1,5}, {5,7}, {3,4,7}, {2}, {4,5}, {1,2}};
	
	public static void bfs(int n) {
		Queue<Integer> q = new LinkedList<>();
		
		q.offer(n); // 넣
		
		visited[n] = true; // 방
		
		while (!q.isEmpty()) { // 반
			int x = q.poll(); // 빼
			
			System.out.println(x + " "); // 출
			
			for (int i = 0; i < graph.get(x).size(); i++) { // 반
				int y = graph.get(x).get(i);
				
				if (!visited[y]) {
					q.offer(y); // 넣
					visited[y] = true; // 방
				}
			}
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		for (int i = 0; i < 9; i++) {
			graph.add(new ArrayList<>());
		}
		
		// 0번째는 생략
		
		graph.get(1).add(2);
		graph.get(1).add(3);
		graph.get(1).add(8);
		
		graph.get(2).add(1);
		graph.get(2).add(6);
		graph.get(2).add(8);
		
		graph.get(3).add(1);
		graph.get(3).add(5);
		
		graph.get(4).add(5);
		graph.get(4).add(7);
		
		graph.get(5).add(3);
		graph.get(5).add(4);
		graph.get(5).add(7);
		
		graph.get(6).add(2);
		
		graph.get(7).add(4);
		graph.get(7).add(5);
		
		graph.get(8).add(1);
		graph.get(8).add(2);
		
		bfs(1); // 1부터
	}
}

BFS 알고리즘 문제 풀이 Java

import java.util.ArrayList;

public class DepthFirstSearch {
	
	// DFS
	// [DFS 알고리즘] 스택 사용 // peek() : Stack 최상단에 있는 top data 반환한다(Stack에서 꺼내진 않음) // pop() : Stack에 있는 데이터 꺼낸다 // push() : Stack에 데이터를 삽입한다 // isEmpty() : Stack 비어있는지 확인한다 // empty() : Stack을 초기화한다 // size() : Stack Size를 반환한다
	// (6)--(2)--(1)--(3)--(5)
	//       |  /           |  \
	//      (8)            (4)--(7)
	
	public static boolean[] visited = new boolean[9];
	public static ArrayList<ArrayList<Integer>> graph = new ArrayList<>(); // 2차원 배열 또는 리스트 활용하자
//	public static int[][] arr = {{}, {2,3,8}, {1,6,8}, {1,5}, {5,7}, {3,4,7}, {2}, {4,5}, {1,2}};
	
	public static void dfs(int n) {
		
		visited[n] = true; // 방
		
		System.out.println(n + " "); // 출
		
		for (int i = 0; i < graph.get(n).size(); i++) {
			
			int x = graph.get(n).get(i);
			
			if (!visited[x]) {
				dfs(x);
			}
		}
		
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		for (int i = 0; i < 9; i++) {
			graph.add(new ArrayList<>());
		}
		
		// 0번째는 생략
		
		graph.get(1).add(2);
		graph.get(1).add(3);
		graph.get(1).add(8);
		
		graph.get(2).add(1);
		graph.get(2).add(6);
		graph.get(2).add(8);
		
		graph.get(3).add(1);
		graph.get(3).add(5);
		
		graph.get(4).add(5);
		graph.get(4).add(7);
		
		graph.get(5).add(3);
		graph.get(5).add(4);
		graph.get(5).add(7);
		
		graph.get(6).add(2);
		
		graph.get(7).add(4);
		graph.get(7).add(5);
		
		graph.get(8).add(1);
		graph.get(8).add(2);
		
		dfs(1); // 1부터
	}
}

DFS 알고리즘 문제 풀이 Java 

DFS : 한 드라마를 몰아서 본다(Stack이나 재귀함수를 사용)

BFS : 여러 드라마를 한 편씩 본다.(Queue나 LinkedList를 사용)

DFS  또는 BFS로 풀어야 하는 대표적인 유형

1. 경로 탐색 유형(최단거리, 시간)
2. 네트워크 유형(연결)
3. 조합 유형(모든 조합 만들기)

DFS가 동작 검증이 쉽다.

하나씩 조합을 만들어서 정답과 비교하기 때문에 조합이 잘 나왔는지 확인이 쉽다.

하지만 수행 시간 관점에서는 복불복

운이 좋으면 첫 번째 조합이 최적의 답, 최악의 경우에는 모든 조합을 다 만들어 보면서 시간을 낭비하게 된다.

BFS는 한 번에 여러 조합들을 한 칸 한 칸씩 만들다 보니 조합이 완성되어 정답과 비교하는 시점에
언제 이렇게 만들어졌는지 또는 어디서부터 틀린 건지 분석하기가 까다롭다.

초반에는 느려 보일 수 있지만 하나의 정답만 찾고 나면 나머지 경우의 수는 정답에서 제외된다.

가장 먼저 넣었던 것을 꺼내기 => 연결된 점을 Queue에 넣기 => Queue가 비워질 때까지 반복

코딩 테스트에서 앞에 출제된 문제는 DFS로, 뒤에 출제된 문제는 탐색 시간이 오래 걸릴 거 같다면 BFS로 푸는 것을 추천한다.

public class Greedy {
	
	// 그리디
	// 금액 n과 거스름돈 단위 배열 arr이 주어질 때 최소한의 동전 갯수로 거스름돈을 주려고 한다.
	
	public static void solution(int n, int[] arr) {
		int cnt = 0;
		int val = 0;
		
		for (int i = 0; i < arr.length; i++) {
			cnt += n / arr[i];
			n = n % arr[i];
			
			if (n == 0) {
				System.out.println(cnt + "개의 동전만으로 거스름돈 가능");
				break;
			}
		}
		
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int n = 1260;
		int[] arr = {500, 100, 50, 10}; // 큰 단위가 작은 단위의 배수이므로 큰 단위부터 나눠도 최적의 해 보장(정당성 분석)
		
		solution(n, arr);
	}
}

Greedy 알고리즘 문제 풀이 Java

[Java] PCCP 모의고사 1회 외톨이 알파벳 : https://dev-skill.tistory.com/15

[Java] PCCP 모의고사 1회 체육대회 : https://dev-skill.tistory.com/16

[Java] PCCP 모의고사 1회 유전법칙 : https://dev-skill.tistory.com/17

[Java] PCCP 모의고사 1회 운영체제 : https://dev-skill.tistory.com/18

프로그래머스 PCCP 모의고사 문제 풀이 Java

import java.util.PriorityQueue;

public class PccpTest1_4 {
	
	// PCCP 모의고사 1회 4번 운영체제
	
	public static long[] solution(int[][] program) {
		long[] answer = {};
		long callTime = 0; // OS 호출 시각
		int runningTime = 0; // OS 수행 시간
		long totalRunningTime = 0; // 전체 OS 종료까지 총 소요 시간
		long blankTime = 0; // OS가 실행중이지 않은 시간
		
		answer = new long[11]; // 크기 11 고정
		
		// STEP 1. ORDER BY 호출 시각, 점수인 우선순위 큐 만들기(전체 OS 담을 우선순위 큐)
		PriorityQueue<Os> osQ = new PriorityQueue<>();
		
		// STEP 2. 1번 우선순위 큐에 program 배열의 OS 담기
		for (int i = 0; i < program.length; i++) {
			osQ.add(new Os(program[i][0], program[i][1], program[i][2]));
		}
		
		// STEP 3. ORDER BY 점수, 호출 시각인 우선순위 큐 만들기(호출 시각 지난 OS 담을 우선순위 큐) => 호출 시각이 지난 OS들은 점수가 낮은 순서대로 실행된다.
		PriorityQueue<WaitingOs> waitingOsQ = new PriorityQueue<>();
		
		// STEP 4. 시간 계산에 사용될 임시 Os, WaitingOs 변수 선언
		Os tempOs = null;
		WaitingOs tempWaitingOs = null;
		
		// STEP 5. 제일 처음 실행될 OS 꺼내기
		Os os = osQ.poll();
		
		callTime = os.getCallTime();
		runningTime = os.getRunningTime();
		
		blankTime = callTime; // 0초에 바로 실행되지 않는 경우도 있을 수 있기 때문에 blankTime 계산해주기
		
		totalRunningTime += blankTime; // 총 소요 시간에 blankTime 더하기
		totalRunningTime += runningTime; // 총 소요 시간에 수행 시간 더하기
		
		// STEP 6. 두 개의 큐가 모두 비워질 때까지 반복
		while (!osQ.isEmpty() || !waitingOsQ.isEmpty()) { // 두 개의 큐 중 어느 하나라도 OS가 담겨있다면 반복
			
			// osQ에 OS가 담겨있다면
			if (!osQ.isEmpty()) {
				
				// 실행 중인 OS로 인해 호출 시각이 지난 OS가 있다면 waitingOsQ(호출 시각이 지난 OS들만 모여있으며, 이 경우 점수가 낮은 OS가 우선적으로 실행될 수 있게 배치)로 보내기
				if (totalRunningTime >= osQ.peek().getCallTime()) {
					tempOs = osQ.poll();
					waitingOsQ.offer(new WaitingOs(tempOs.getGrade(), tempOs.getCallTime(), tempOs.getRunningTime()));
					continue; // 더 있다면 반복 수행되도록 처리
				}
				
				// 이 곳으로 내려왔다는 것은 osQ에 OS가 남아 있으며, waitingOsQ로 보낼 조건에 부합하는 OS가 없다는 것을 의미
				// 여기서 waitingOsQ가 비어있다면 => 즉, 다음 실행될 osQ의 OS가 바로 이어서 실행되지 않기 때문에 waitingOsQ에 보내지 못한 거라면
				if (waitingOsQ.isEmpty()) {
					// blankTime과 runningTime 계산
					tempOs = osQ.poll();
					
					blankTime = (tempOs.getCallTime() - totalRunningTime); // blankTime이 있다는 것을 의미하므로 blankTime 계산해주기
					
					totalRunningTime += (blankTime + tempOs.getRunningTime()); // 총 소요 시간에 blankTime과 수행 시간 더하기
				}
			}
			
			// waitingOsQ에 OS가 담겨있다면
			if (!waitingOsQ.isEmpty()) {
				tempWaitingOs = waitingOsQ.poll();
				
				answer[tempWaitingOs.getGrade()] += (totalRunningTime - tempWaitingOs.getCallTime()); // 해당 점수의 대기 시간 더하기
				
				totalRunningTime += tempWaitingOs.getRunningTime(); // 총 소요 시간에 해당 점수의 수행 시간 더하기
			}
		}
		
		answer[0] = totalRunningTime; // answer[0]에는 총 소요 시간을 넣어준다.
		
		for (int i = 0; i < answer.length; i++) {
			System.out.print(answer[i] + " ");
		}
		
		return answer;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[][] program = {{2, 0, 10}, {1, 5, 5}, {3, 5, 3}, {3, 12, 2}}; // 점수, 호출 시각, 수행 시간 // 20, 5, 0, 16, 0, 0, 0, 0, 0, 0, 0 // 종료 시각, 점수 1 ~ 10 총 대기 시간
//		int[][] program = {{3, 6, 4}, {4, 2, 5}, {1, 0, 5}, {5, 0, 5}}; // 19 0 0 4 3 14 0 0 0 0 0
//		int[][] program = {{3, 6, 4}, {4, 2, 5}, {1, 0, 5}, {4, 1, 10}, {5, 0, 5}, {2, 0, 8}}; // 37 0 5 7 41 32 0 0 0 0 0
		
		System.out.println(solution(program));
	}
}

public class Os implements Comparable<Os> { // 호출 시각, 점수 기준
	
	private int grade = 0; // 점수
	private long callTime = 0; // 호출 시각
	private int runningTime = 0; // 수행 시간
	
	public Os(int grade, long callTime, int runningTime) {
		this.grade = grade;
		this.callTime = callTime;
		this.runningTime = runningTime;
	}
	
	public int getGrade() {
		return this.grade;
	}
	
	public long getCallTime() {
		return this.callTime;
	}
	
	public int getRunningTime() {
		return this.runningTime;
	}

	@Override
	public int compareTo(Os otherNode) { // ORDER BY callTime, grade
		// TODO Auto-generated method stub
		if (this.callTime == otherNode.callTime) { // callTime이 같을 경우
			
			if (this.grade - otherNode.grade >= 0) { // grade 기준 오름차순 정렬
				return 1;
			} else {
				return -1;
			}
		} else { // callTime이 같지 않을 경우
			
			if (this.callTime - otherNode.callTime >= 0) { // callTime 기준 오름차순 정렬
				return 1;
			} else {
				return -1;
			}
		}
	}
}

public class WaitingOs implements Comparable<WaitingOs> { // 점수, 호출 시각 기준
	
	private int grade = 0; // 점수
	private long callTime = 0; // 호출 시각
	private int runningTime = 0; // 수행 시간
	
	public WaitingOs(int grade, long callTime, int runningTime) {
		this.grade = grade;
		this.callTime = callTime;
		this.runningTime = runningTime;
	}
	
	public int getGrade() {
		return this.grade;
	}
	
	public long getCallTime() {
		return this.callTime;
	}
	
	public int getRunningTime() {
		return this.runningTime;
	}

	@Override
	public int compareTo(WaitingOs otherNode) { // ORDER BY grade, callTime
		// TODO Auto-generated method stub
		if (this.grade == otherNode.grade) { // grade가 같을 경우
			
			if (this.callTime - otherNode.callTime >= 0) { // callTime 기준 오름차순 정렬
				return 1;
			} else {
				return -1;
			}
		} else { // grade가 같지 않을 경우
			
			if (this.grade - otherNode.grade >= 0) { // grade 기준 오름차순 정렬
				return 1;
			} else {
				return -1;
			}
		}
	}
}

제출 후 채점하기에서 실패로 뜨는 테스트 케이스들이 많았고, solution 메소드에 문제가 있는 것인지 여러 차례 확인했다.

결론은 solution 메소드에는 문제가 없었고 WaitingOs의 정렬 기준을 '점수'로만 했던 것이 원인이었다.

호출 시각이 지난 OS들은 '점수'가 낮은 순서대로 실행되는 것이 맞지만, '호출 시각' 또한 고려해야 했다는 것을 뒤늦게

깨닫고 WaitingOs의 정렬 기준을 '점수', '호출 시각'으로 변경하여 문제를 해결하였다.

프로그래머스 PCCP 모의고사 문제 풀이 Java