java 알고리즘 스터디 11주차

15683 감시

📌문제 링크

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

💡 문제 풀이

카메라마다 바라볼 수 있는 모든 경우의 수를 계산해 dfs로 풀었다.
처음에는 메모리 좀 아껴보겠다고 감시 방향을 map에 -1로 표시했다가 다시 0으로 초기화하는 방법을 썼는데, 다른 카메라가 바라보는 경로인데도 0으로 초기화하는 경우가 생겨 오답이 나왔다.
map을 복사해서 dfs를 하는 방식으로 구현하니 정답이었다..

📋코드

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

public class Main {
	static List<int[]> cctvList;
	static int N, M;
	static int tvNum = 0, answer = Integer.MAX_VALUE;
	// 상 우 하 좌
	static int[] dr = { -1, 0, 1, 0 };
	static int[] dc = { 0, 1, 0, -1 };

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stk = new StringTokenizer(br.readLine());

		N = Integer.parseInt(stk.nextToken());
		M = Integer.parseInt(stk.nextToken());

		int[][] map = new int[N][M];
		cctvList = new ArrayList<int[]>();

		// map 입력
		for (int i = 0; i < N; i++) {
			stk = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(stk.nextToken());
				if (isCCTV(map[i][j])) {
					cctvList.add(new int[] { i, j });
				}
			}
		}

		// cctv의 개수
		tvNum = cctvList.size();
		
		dfs(0, map);

		System.out.println(answer);
	}

	private static void dfs(int cnt, int[][] map) {
		if (cnt == tvNum) {
        	// 모든 cctv의 방향을 체크했다면 사각지대 크기 구함
			answer = Math.min(answer, getBlind(map));
			return;
		}

		int i = cctvList.get(cnt)[0];
		int j = cctvList.get(cnt)[1];
		
		int[][] tmp = new int[N][M];

		for (int d = 0; d < 4; d++) {
			copyMap(map, tmp); // map 복사
            
            // cctv 종류에 따라 다르게 처리
			switch (map[i][j]) {
			case 1:
            	// 한 방향만 감시
				fill(tmp, i, j, d, -1);
				dfs(cnt + 1, tmp);
				break;
			case 2:
            	// 상하 / 좌우 2가지로만 감시 가능
                // -> 2번만 반복해도 됨
				if (d > 1) break;
                // 반대방향 감시
				fill(tmp, i, j, d, -1);
				fill(tmp, i, j, (d + 2) % 4, -1);
				dfs(cnt + 1, tmp);
				break;
			case 3:
            	// 직각 방향 감시
				fill(tmp, i, j, d, -1);
				fill(tmp, i, j, (d + 1) % 4, -1);
				dfs(cnt + 1, tmp);
				break;
			case 4:
            	// 한 방향만 빼고 감시
				fill(tmp, i, j, d, -1);
				fill(tmp, i, j, (d + 1) % 4, -1);
				fill(tmp, i, j, (d + 2) % 4, -1);
				dfs(cnt + 1, tmp);
				break;
			case 5:
				if (d > 0) break; // 한 번만 반복해도 됨
                // 모든 방향 감시
				fill(tmp, i, j, d, -1);
				fill(tmp, i, j, (d + 1) % 4, -1);
				fill(tmp, i, j, (d + 2) % 4, -1);
				fill(tmp, i, j, (d + 3) % 4, -1);
				dfs(cnt + 1, tmp);
				break;
			}
		}
		return;
	}

	
    // map 복사
	private static void copyMap(int[][] origin, int[][] copied) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				copied[i][j] = origin[i][j];
			}
		}
	}

	// map 채우기
	private static void fill(int[][] map, int row, int col, int d, int val) {
		row += dr[d];
		col += dc[d];
		while (row > -1 && row < N && col > -1 && col < M) {
			if (map[row][col] == 6) // cctv는 벽을 통과할 수 없음
				break;
			
            // cctv는 cctv를 통과할 수 있음
			if (!isCCTV(map[row][col])) {
				map[row][col] = val;
			}
			row += dr[d];
			col += dc[d];
		}

	}
	
    // cctv인지 검사
	private static boolean isCCTV(int num) {
		if (num > 0 && num < 6) return true;
		return false;
	}

	// 사각지대 계산
	private static int getBlind(int[][] map) {
		int cnt = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (map[i][j] == 0)
					cnt++;

			}
		}

		return cnt;
	}

}

메모리 : 28868KB, 시간 : 280ms

1043 거짓말

📌문제 링크

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

💡 문제 풀이

union-find 알고리즘을 사용했다.
처음에는 입력을 받으면서 파티에 진실을 아는 사람이 있다면 Set에 추가하는 방법으로 구현했는데, 그러면 나중 파티에서 진실을 아는 사람을 만날 경우를 계산하지 못했다..

풀이 방법
1. 같은 파티에 간 사람들끼리 모두 union한다.
2. 파티에 있는 사람 중 진실을 아는 사람과 같은 집합에 있는 사람이 없으면 거짓말을 할 수 있다

📋코드

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

public class Main {
	static int[] parents, truth;
	static int truthNum;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stk = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(stk.nextToken());
		int M = Integer.parseInt(stk.nextToken());
		
        // union-find를 위한 parents 배열 초기화
		parents = new int[N+1];
		for (int i = 1; i <= N; i++) {
			makeSet(i);
		}
		
		// 진실을 아는 사람 입력
		stk = new StringTokenizer(br.readLine());
		truthNum = Integer.parseInt(stk.nextToken());
		
        // 진실을 아는 사람이 없으면 모든 파티에서 거짓말할 수 있음
		if (truthNum == 0) {
			System.out.println(M);
			System.exit(0);
		}
		
		truth = new int[truthNum];
		for (int i = 0; i < truthNum; i++) {
			truth[i] = Integer.parseInt(stk.nextToken());
            // 진실을 아는 사람끼리 union
			if (i > 0) union(truth[i-1], truth[i]);
		}
		
		// 파티 입력
		int size;
		ArrayList<Integer>[] party = new ArrayList[M];
		for (int p = 0; p < M; p++) {
			stk = new StringTokenizer(br.readLine());
			size = Integer.parseInt(stk.nextToken()); // 파티에 온 사람의 수
			party[p] = new ArrayList<>();
			
			for (int i = 0; i < size; i++) {
				party[p].add(Integer.parseInt(stk.nextToken()));
                
				// 파티에 온 사람끼리 모두 union
				if (i > 0) union(party[p].get(i-1), party[p].get(i));
			}
		}
		
		int answer = 0;
		for (ArrayList<Integer> p : party) {
        	// 파티에서 거짓말을 할 수 있는지 검사
			if (canLie(p)) answer++;
		}
		
		System.out.println(answer);
	}

	private static boolean canLie(ArrayList<Integer> p) {
		for (int n : p) {
        	// 진실을 알고 있는 사람과 같은 집합에 있다면 거짓말할 수 없음
            // 모두 union했으므로 진실을 알고있는 0번째 사람을 기준으로 검사
			if(findSet(truth[0]) == findSet(n)) return false;
		}
		return true;
	}

	private static void union(int u, int v) {
		parents[findSet(u)] = findSet(v);
	}

	private static int findSet(int v) {
		if (parents[v] == v) return v;
		return parents[v] = findSet(parents[v]);
	}

	private static void makeSet(int v) {
		parents[v] = v;
	}


}

메모리 : 16128KB, 시간 : 164ms

9935 문자열 폭발

📌문제 링크

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

💡 문제 풀이

다른 사람 코드를 참고해서 풀었다.
문자열을 앞부터 차례로 stack에 넣고, 맨 위 문자열이 폭발 문자열이면 pop한다.
이 과정을 반복하면 모든 폭발 문자열을 없앨 수 있다!!

📋코드

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

public class Main {
	static int bomblen;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String str = br.readLine(); // 문자열
		String bomb = br.readLine(); // 폭발 문자열
		bomblen = bomb.length(); // 폭발 문자열 길이
		
		Stack<Character> stack = new Stack<>();
		
		for (int i = 0; i < str.length(); i++) {
        	// 차례로 stack에 넣음
			stack.add(str.charAt(i));
			
            // stack의 크기가 폭발 문자열 길이 이상이라면 폭발 문자열 검사
			if (stack.size() >= bomblen) {
            	// 폭발 문자열이면 모두 pop
				if (check(stack, bomb)) { 
					for (int j = 0; j < bomblen; j++) {
						stack.pop();
					}
				}
			}
		}
		
        // 남은 문자열이 없으면 FRULA 출력
		if (stack.size() == 0) System.out.println("FRULA");
		else { // 남은 문자열 출력
			StringBuilder sb = new StringBuilder();
			for (char c : stack) {
				sb.append(c);
			}
			System.out.println(sb.toString());
		}
		
	}
	
    // stack의 top 문자열이 폭발 문자열과 같은지 검사
	private static boolean check(Stack<Character> stack, String bomb) {
		for (int i = 0; i < bomblen; i++) {
			if (stack.get(stack.size() - bomblen + i) != bomb.charAt(i)) return false; 
		}
		return true;
	}

}

메모리 : 33768KB, 시간 : 476ms