선장 일지

• 생각

19996~19999까지 곱하게 된다면 5자리수 * 5자리수 * 5자리수 * 5자리수 이므로 숫자가 조단위가 됩니다. 이 점에 유의하셔야 시간초과를 피할 수 있다.

• 코드

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

public class Main {
	static long answer;

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(answer%10);
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		long input = Long.parseLong(br.readLine());
		answer =1;
		
		for(int i=1;i<=input;i++) {
			answer*=i;
			answer %= 1000000000;
			while (answer % 10 == 0)
			     answer /= 10;
		}
	}
}

• 생각

backtraking 메소드에서 문자열에 1,2,3을 계속 추가시키면서 좋을수열(PossibleNumber 메소드에서 체크)인 수열만 계속 backtraking하다가 수의 길이가 N이면 출력 후 종료(제일 적은 수가 먼저 도착하기 때문)

• 코드

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

public class Main {
	static int N;

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

		N = Integer.parseInt(br.readLine());

		backtracking("");
	}

	private static void backtracking(String s) {
		if (s.length() == N) {
			System.out.println(s);
			System.exit(0);
		}

		for (int i = 1; i <= 3; i++) {
			if (PossibleNumber(s + i))
				backtracking(s + i);
		}
	}

	private static boolean PossibleNumber(String s) {
		int length = s.length();
		for (int i = 1; i <= length/2; i++) {
			String frontString = s.substring(length-i*2, length-i);
			String backString = s.substring(length-i, length);
			if (frontString.equals(backString))
				return false;
		}

		return true;
	}
}

• 생각

브루트포스 문제로 모든 경우의 수를 다 확인해봐야되는 문제이다.

문제를 읽으면서 dfs 방식으로 풀면 된다고 생각이 들었다. (모든 경우의 수를 볼 때 많이 사용함)

dfs방식

1. N개의 지역을 지역1, 지역2로 할당하면서 돌린다.

2. N개 모두 지역이 할당되면 area1, area2로 인구 수를 구해준다.

3. area1, area2 모두 연결되어 있는지 확인한다.

4. 모두 연결되어 있다면 두 지역의 인구 수 차를 구해 업데이트 시킨다.

• 코드

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

public class Main {
	static int N, answer;
	static int[] population, area;
	static boolean[][] connect;
	static boolean[] check;	

	public static void main(String[] args) throws Exception {
		SetData();
		dfs(1);
		if(answer == Integer.MAX_VALUE)
			answer = -1;
		System.out.println(answer);
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		N = Integer.parseInt(br.readLine());
		answer = Integer.MAX_VALUE;
		population = new int[N + 1];
		area = new int[N + 1];
		connect = new boolean[N+1][N+1];
		
		st = new StringTokenizer(br.readLine());
		for(int i = 1; i <= N; i++) {
			population[i] = Integer.parseInt(st.nextToken()); 
		}

		for(int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			int count = Integer.parseInt(st.nextToken());
			for(int j = 0; j < count; j++) {
				int temp = Integer.parseInt(st.nextToken());
				connect[i][temp] = true;
				connect[temp][i] = true;
			}
		}
	}
	
	static void dfs(int count) {
        if(count == N+1) {
        	// 나눈 지역의 인구 수를 구함
            int area1 = 0, area2 = 0;
            for(int i=1; i<=N; i++) {
                if(area[i] == 1)
                    area1 += population[i];
                else
                    area2 += population[i];
            }
            
            // 두 지역으로 나누어 져있는지 체크
            check = new boolean[N+1];
            int result = 0;
            for(int i=1; i<=N; i++) {
                if(!check[i]) {
                    checkArea(i, area[i]);
                    result++;
                }
            }
            
            // 두 지역으로 나누어져 있으면 두 지역 값의 차를 구해서 최소 값 도출
            if(result == 2) {
                if(answer > Math.abs(area1 - area2))
                    answer =  Math.abs(area1 - area2);
            }
            return;
        }
        
        // 지역 1 포함
        area[count] = 1;
        dfs(count+1);
        
        // 지역 2 포함
        area[count] = 2;
        dfs(count+1);
	}
	
    private static void checkArea(int index, int number) {
        check[index] = true;
        for(int i=1; i<=N; i++) {
            if(connect[index][i] && !check[i] && area[i]==number)
                checkArea(i, number);
        }
    }
}

• 생각

문제를 보면 무조건 1과 연결되어 있는 컴퓨터 개수를 새는 문제이다.

컴퓨터 1과 연결되어 있으면 계속 깊이탐색을 해서 연결된 컴퓨터 갯수를 카운트하면 답은 쉽게 나온다.

• 코드

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

public class Main {
	static int a, b, answer;
	static boolean[][] graph;	
	static boolean[] check;	

	public static void main(String[] args) throws Exception {
		SetData();
		dfs(1);
		System.out.println(answer);
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		a = Integer.parseInt(br.readLine());
		b = Integer.parseInt(br.readLine());

		graph = new boolean[a + 1][a + 1];
		check = new boolean[a + 1];

		for (int i = 1; b >= i; ++i) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int first = Integer.parseInt(st.nextToken());
			int second = Integer.parseInt(st.nextToken());
			graph[first][second] = true;
			graph[second][first] = true;
		}
	}
	
	static void dfs(int start) {
		check[start] = true;
		for (int i = 1; a >= i; ++i) {	        								
			if (graph[start][i] == true && check[i] == false) {
					dfs(i);		
					answer++;	
				}
			}
		}
}

• 생각

DFS를 통해 N자리의 각 자리 모두 소수인 숫자만 추가해주었다.

• 코드

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

public class Main {
	static int N;
	static StringBuilder sb;

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(sb.toString());
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		sb = new StringBuilder();

		dfs("");
	}

	private static void dfs(String s) {
		if (s.length() == N) {
			sb.append(s + '\n');
			return;
		}
		for (int i = 1; i <= 9; i++) {
			if (Prime(Integer.parseInt(s + i))) {
				dfs(s + i);
			}
		}

	}

	private static boolean Prime(int num) {
		if (num == 1)
			return false;

		for (int i = 2; i <= Math.sqrt(num); i++) {
			if (num % i == 0)
				return false;
		}
		return true;
	}
}

• 생각

지금보다 적은 수의 벽을 부수고 왔다면 큐에 넣으면서 bfs를 돌리면 될 것 같다.

• 코드

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

public class Main {
    static int N;
    static int[][] array;
    static int[][] check;
    static int[] x = {-1, 1, 0, 0};
    static int[] y = {0, 0, -1, 1};
	
    public static void main(String[] args) throws Exception {
        SetData();
        bfs(0, 0);
        System.out.println(check[N-1][N-1]);
    }
	private static void SetData() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        array = new int[N][N];
        check = new int[N][N];

        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                check[i][j]=Integer.MAX_VALUE;
            }
        }

        for(int i=0; i<N; i++) {
            String input = br.readLine();
            for(int j=0; j<N; j++) {
                array[i][j] = 1 - (input.charAt(j) - '0');
            }
        }
	}
	
    public static void bfs(int a, int b) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[] {a,b});
        check[0][0]=0;
        
        while(!queue.isEmpty()){
            int location[] = queue.poll();     

            for(int direction = 0; direction<4; direction++){
                int r = location[0] + x[direction];
                int c = location[1] + y[direction];

                if(r >= 0 && c >= 0 && r < N && c < N) {
                    if(check[r][c] > check[location[0]][location[1]]+array[r][c]) {
                        check[r][c] = check[location[0]][location[1]]+array[r][c];
                        queue.add(new int[] {r,c});
                    }
                }
            }
        }
    }
}

• 생각

dfs를 통해 상하좌우 붙어있는 색상 중 선택한 하나의 색상과 같다면, 같은 하나의 구역으로 만들면 된다.

적록색약 환자면 적색, 녹색 색상도 똑같이 보고 같은 하나의 구역으로 만든다.

• 코드

정답 코드 : dfs로 풀었다. 같은 문자면 ture해가면서 깊이 들어감. 적록색약은 R을 G로 모두 바꿔준다음에 똑같은 작업을 해주었다.

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

public class Main {
	static int N, count, colorWeeknessCount;
	static char[][] array;
	static boolean[][] check;
	static boolean colorWeakness;
	static int[] x = { -1, 1, 0, 0 };
	static int[] y = { 0, 0, -1, 1 };

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.print(count + " " + colorWeeknessCount);
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());

		array = new char[N][N];
		check = new boolean[N][N];
		colorWeakness = false;
		count = 0;
		colorWeeknessCount = 0;

		for (int i = 0; i < N; i++) {
			String s = br.readLine();
			for (int j = 0; j < N; j++) {
				array[i][j] = s.charAt(j);
			}
		}

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (!check[i][j]) {
					check[i][j] = true;
					bfs(i, j, array[i][j]);
					count++;
				}
			}
		}

		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				check[i][j] = false;

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (array[i][j] == 'G')
					array[i][j] = 'R';
			}
		}

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (!check[i][j]) {
					check[i][j] = true;
					bfs(i, j, array[i][j]);
					colorWeeknessCount++;
				}
			}
		}
	}
	
	private static void bfs(int a, int b, char temp) {
		Queue<int[]> queue = new LinkedList<>();
		queue.offer(new int[] { a, b });

		while (!queue.isEmpty()) {
			int location[] = queue.poll();

			for (int direction = 0; direction < 4; direction++) {
				int r = location[0] + x[direction];
				int c = location[1] + y[direction];

				if (r >= 0 && c >= 0 && r < N && c < N) {
					if (array[r][c] == temp && !check[r][c]) {
						check[r][c] = true;
						queue.offer(new int[] { r, c });
					}
				}
			}
		}
	}
}

• 생각

dfs를 돌리면서 방향은 X+1, Y가 1,0,-1방향으로 가면서 작동하게 하면 된다.

단, queue로 구현하니 메모리초과가 떠서, 재귀방식으로 구현하였습니다.

• 코드

정답 코드 : dfs 방식으로 풀었다.

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

public class Main {
	static int R, C, answer;
	static int[][] array;
	static boolean[][] check;
	static int[] x = { -1, 0, 1 };
	static int[] y = { 1, 1, 1 };
	
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		SetData();
		System.out.print(answer);
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		answer = 0;

		array = new int[R][C];
		check = new boolean[R][C];

		for (int i = 0; i < R; i++) {
			String s = br.readLine();
			for (int j = 0; j < C; j++) {
				array[i][j] = s.charAt(j);
			}
		}
	
		for (int i = 0; i < R; i++) 
			answer += dfs(i, 0);
	}
	
	public static int dfs(int a, int b) {
		if (b == C - 1) 
			return 1;

		for (int direction = 0; direction < 3; direction++) {
			int r = a + x[direction];
			int c = b + y[direction];

			if (r >= 0 && c >= 0 && r < R && c < C) {
				if (array[r][c] == '.' && !check[r][c]) {
					check[r][c] = true;
					if(dfs(r, c) == 1) return 1;
				}
			}
		}
		return 0;
	}
}