똥대

1. 언어 : JAVA

2. 난이도 : Gold 4

15684번: 사다리 조작

 

www.acmicpc.net

3. 풀이

생각해보면 쉬운 문제다 2개의 함수의 구현이 필요하다.

DPS와 check 함수

dps 는 말그래도 depth 탐색 함수고

check는 사다리가 정답(1->1, 2->2, 3->3 .. N->N)인지 확인해주는 함수이다.

또한 map[][] 에 넣을때 오른쪽으로 갈수 있는 아이는 1, 왼쪽으로 갈수있는 아이는 -1로 저장하였다.

그리고 알아야 할 점은, 브루트포스이며 백트래킹을 사용한다.

소스코드는 다음과 같다.

4. 소스코드

import java.util.*;
import java.io.*;

public class Main {
	public static BufferedReader br = null;
	public static BufferedWriter bw = null;
	public static int N = 0;
	public static int M = 0;
	public static int H = 0;
	public static int result = 4;
	public static void main(String [] args) throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		String [] input = br.readLine().split(" ");
		N = Integer.parseInt(input[0]);
		M = Integer.parseInt(input[1]);
		H = Integer.parseInt(input[2]);
		
		int [][] map = new int[H+2][N+1];
		
		for(int i=0; i<M; i++) {
			input = br.readLine().split(" ");
			int a = Integer.parseInt(input[0]);
			int b = Integer.parseInt(input[1]);
			map[a][b] = 1;
			map[a][b+1] = -1;
		}

		dfs(1, 1, map, 0);			
		
		if(result <= 3) {
			bw.write(result + "\n");
		}
		else {
			bw.write("-1");
		}
		bw.flush();
	}
	public static void dfs(int y, int x, int [][] map, int ladder) throws IOException {
		if(ladder > 3) {
			return;
		}
		
		if(check(map)) {
			result = Math.min(result, ladder);
		}
		
		for(int i=y; i<=H; i ++) {
			for(int j=1; j<=N-1; j ++) {
				if(map[i][j] == 0 && map[i][j+1] == 0) {
					map[i][j] = 1;
					map[i][j+1] = -1;
					dfs(i, j, map, ladder+1);
					map[i][j] = 0;
					map[i][j+1] = 0;
				}
			}
		}
	}
	public static int [][] copy(int [][] map) {
		int [][] copy = new int[H+2][N+1];
		for(int i=0; i<H+2; i++) {
			for(int j=0; j<N+1; j++) {
				copy[i][j] = map[i][j];
			}
		}
		return copy;
	}
	
	public static boolean check(int [][] map) throws IOException {
		int y = 0;
		int x = 0;
		for(int n=1; n<=N; n++) {
			y = 1;
			x = n;
			while(true) {
				if(map[y][x] == 1) {
					y ++;
					x ++;
				}
				else if (map[y][x] == -1) {
					y ++;
					x --;
				}
				else if(map[y][x] == 0) {
					y ++;
				}
				
				if(y == H+1) {
					if(x == n) {
						
					}
					else {
						return false;
					}
					break;
				}
			}
		}
		
		return true;
	}
}

1. 언어 : JAVA

1043번: 거짓말

 

www.acmicpc.net

2. 난이도 : Gold 4

3. 풀이

입력으로 다음과 같이 주어진다.

여기서 핵심은 문제를 이해하는 것이다. (맨날 덜렁대서 문제를 잘못이해해서 잘못풀었음..)

국어 먼저해야하나 하,,,

Anyway

문제를 이해했다고(?) 가정하고,

가장먼저 떠올라야 하는건 DFS로 파티에서 진실을 알고 있는 사람과 그 파티에 속한 사람 전부 DFS를 돌려주는것이다.

(왜냐하면 진실을 알고있는 자에게 과장할 수가 없으니까!)

이게 무슨소리냐?

위의 예를 보면 1번이 진실을 알고 있고,

파티는 총 5개 열린다.

파티1 -> 1번 참가

파티2 -> 2번 참가

파티3 -> 3번 참가

파티4 -> 4번 참가

파티5 -> 4, 1번 참가

무슨 파티에 인원이 1명이냐? 

이런식이다. 그러면 일단 파티1과 파티5에서는 허풍을 떨수가 없다.

그 다음 DFS를 돌려야하는데 파티1은 1번밖에 없으니 더이상 진행할 수 없고,

파티 5에서 4번이 다른파티에서 만약 참여했으면 그 파티에서도 과장을 할 수 없는 것이다.

따라서 4번이 있는 파티 4번에서도 과장 안된다.

따라서 파티2, 3에서만 과장을 할 수 있어서, 2가 답이다.

또 다른 예를 보면

진실 알고있는자 1

파티1 : 1,2

파티2 : 2,3

파티3 : 3,4,5

파티4 : 4, 6

파티5 : 5, 7

파티1번 시작 -> DFS(2번이 속한 파티도 안됨)

파티2번 시작 -> DFS(3번이 속한 파티도 안됨)

파티3번 시작 -> DFS(4번이 속한 파티도 안됨, 5번이 속한 파티도 안됨)

파티4, 파티5 <- 4번과 5번에 의해서 과장할 수 없음

이런식 인 것이다.

항상 알고리즘은 생각하기가 어렵지 생각하고 나면 구현은 딱히 어렵지 않다.

이번 문제 역시 현타왔다.

꾸준히 하다보면 늘것지뭐..

4. 소스코드

import java.util.*;
import java.io.*;
public class Main {
	public static BufferedReader br = null;
	public static BufferedWriter bw = null;
	public static int N = 0;
	public static int M = 0;
	public static void main(String [] args) throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		int [] truePeople = new int[N];
		
		st = new StringTokenizer(br.readLine());
		int num = Integer.parseInt(st.nextToken());
		for(int i=0; i<num; i++) {
			truePeople[Integer.parseInt(st.nextToken()) - 1] = 1;
		}
		
		int [] check = new int[M];
		ArrayList <ArrayList <Integer>> party = new ArrayList();
		for(int i=0; i<M; i++) {
			party.add(new ArrayList<Integer>());
			st = new StringTokenizer(br.readLine());
			num = Integer.parseInt(st.nextToken());
			for(int j=0; j<num; j++) {
				int people = Integer.parseInt(st.nextToken()) - 1;
				party.get(i).add(people);
				if(truePeople[people] == 1) {
					check[i] = 1;
				}
			}
		}
		
		//풀이 시작
		for(int i=0; i<M; i++) {
			if(check[i] == 1) {
				check[i] = -1;
				dfs(check, party, i);
			}
		}
		int count = 0;
		if(num == 0) {
			for(int temp : truePeople) {
				if(temp == 1) count ++;
			}
		}
		else {
			for(int temp : check) {
				if(temp == 0) count ++;
			}
			
		}
		bw.write(count + "\n");
		bw.flush();
		bw.close();
		
	}
	public static void dfs(int [] check, ArrayList <ArrayList <Integer>> party, int presentLocation) {
		for(int i=0; i<party.get(presentLocation).size(); i++) {
			for(int j=0; j<party.size(); j++) {
				if(party.get(j).contains(party.get(presentLocation).get(i)) && check[j] != -1) { 
					check[j] = -1;
					dfs(check, party, j);
				}
			}
		}
	}
}