선장 일지

• 생각

문제를 보면 무조건 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;
	}
}

• 생각

fisrtInput이 i까지의 길이, secondInput이 j까지의 길이일 때, dp[i][j]가 있다.

1. first[i]와 second[j]가 같다면, dp[i-1][j-1]+1의 값이 dp[i][j]의 값이 될 것이다. 를 토대로 나옴

2. first[i]와 second[j]가 다르다면, first의 마지막 문자 i를 제외한 dp[i-1][j]의 경우의 수가 될 것이다. 마찬가지로 seond의 마지막 문자 j를 제외한 dp[i][j-1]의 경우의 수가 될 것이다. 여기서 우린 최장길이를 선택하는 것이니, 두 개의 경우의 수 중 큰 값을 가지고 온다. 를 토대로 나왔다.

https://www.youtube.com/watch?v=EAXDUxVYquY를 참고하였다.

• 코드

정답 코드 : LCS 알고리즘의 점화식을 통하여 구현하였다.

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

public class Main {
	static int[][] dp;
	static int firstInputLength, secondInputLength;

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		SetData();
		System.out.println(dp[firstInputLength][secondInputLength]);
	}
	
	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String firstInput = br.readLine();
		String secondInput = br.readLine();

		firstInputLength = firstInput.length();
		secondInputLength = secondInput.length();
		dp = new int[firstInputLength + 1][secondInputLength + 1];
		
		for (int i = 1; i <= firstInputLength; i++) { 
			for (int j = 1; j <= secondInputLength; j++) { 
				if (firstInput.charAt(i - 1) == secondInput.charAt(j - 1)) { 
					dp[i][j] = dp[i - 1][j - 1] + 1;
				} else { 
					dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);				
				}
			}
		}
	}	
}

• 생각

백트래킹(0으로 되돌리는 작업)을 하지않고 했다가 고생좀 했다.. 0이 발견되면 1~9까지 다 넣어보면서 행, 열, 3X3 모두 체크해주면서 true가 반환되면 해당 값을 넣어준뒤 c를 +1해주면서 재귀를 돈다. 여기서 다른 값이 안될 경우가 있기 때문에 가다가 아무작업도 못하고 되돌아올 경우 다시 0으로 돌려주어야 한다.

• 코드

정답 코드 : 백트래킹으로 구현한 코드이다.

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

public class Main {

	static int[][] array;
	static StringBuilder sb;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		array = new int[9][9];
		sb = new StringBuilder();

		for (int i = 0; i < 9; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 9; j++)
				array[i][j] = Integer.parseInt(st.nextToken());
		}

		Sudoku(0, 0);

	}

	static void Sudoku(int r, int c) {

		if (c == 9) {
			sb.append("\n");
			Sudoku(r + 1, 0);
			return;
		}

		if (r == 9) {
			for (int i = 0; i < 9; i++) {
				for (int j = 0; j < 9; j++) {
					System.out.print(array[i][j] + " ");
				}
				System.out.println("");
			}
			System.exit(0);
		}

		if (array[r][c] == 0) {
			for (int i = 1; i <= 9; i++) {
				if (Possible(r, c, i)) {
					array[r][c] = i;
					Sudoku(r, c + 1);
				}
				array[r][c] = 0;
			}
		} else {
			Sudoku(r, c + 1);
		}
	}

	static boolean Possible(int r, int c, int value) {

		// 행
		for (int i = 0; i < 9; i++) {
			if (array[r][i] == value) {
				return false;
			}
		}

		// 열
		for (int i = 0; i < 9; i++) {
			if (array[i][c] == value) {
				return false;
			}
		}

		// 3*3
		int tempR = (r / 3) * 3;
		int tempC = (c / 3) * 3;

		for (int i = tempR; i < tempR + 3; i++) {
			for (int j = tempC; j < tempC + 3; j++) {
				if (array[i][j] == value) {
					return false;
				}
			}
		}

		return true;
	}

}

나중 코드 : 백트래킹으로 구현한 코드이다.

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

public class Main {
	static int[][] array;
	static StringBuilder sb;

	public static void main(String[] args) throws Exception {
		SetData();
		dfs(0, 0);
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		array = new int[9][9];
		sb = new StringBuilder();
		
		for (int i = 0; i < 9; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 9; j++)
				array[i][j] = Integer.parseInt(st.nextToken());
		}

	}

	static void dfs(int r, int c) {

		if (c == 9) {
			dfs(r + 1, 0);
			return;
		}

		if (r == 9) {
			for (int i = 0; i < 9; i++) {
				for (int j = 0; j < 9; j++) {
					sb.append(array[i][j] + " ");
				}
				sb.append("\n");
			}
			System.out.println(sb);
			System.exit(0); // 이렇게 바로 끝내줘야지 시간초과가 나지 않음
		}

		if (array[r][c] == 0) {
			for (int i = 1; i <= 9; i++) {
				if (Sudoku(r, c, i)) {
					array[r][c] = i;
					dfs(r, c + 1);
				}
				array[r][c] = 0;
			}
		} else {
			dfs(r, c + 1);
		}
	}

	static boolean Sudoku(int r, int c, int value) {
		// 행
		for (int i = 0; i < 9; i++) {
			if (array[r][i] == value) {
				return false;
			}
		}

		// 열
		for (int i = 0; i < 9; i++) {
			if (array[i][c] == value) {
				return false;
			}
		}

		// 3*3
		int tempR = (r / 3) * 3;
		int tempC = (c / 3) * 3;

		for (int i = tempR; i < tempR + 3; i++) {
			for (int j = tempC; j < tempC + 3; j++) {
				if (array[i][j] == value) {
					return false;
				}
			}
		}

		return true;
	}
}

• 생각

백트래킹(0으로 되돌리는 작업)을 하지않고 했다가 고생좀 했다.. 0이 발견되면 1~9까지 다 넣어보면서 행, 열, 3X3 모두 체크해주면서 true가 반환되면 해당 값을 넣어준뒤 c를 +1해주면서 재귀를 돈다. 여기서 다른 값이 안될 경우가 있기 때문에 가다가 아무작업도 못하고 되돌아올 경우 다시 0으로 돌려주어야 한다.

• 코드

정답 코드 : 백트래킹을 통해 구현하였다.

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

public class Main {

	static int[][] array;
	static StringBuilder sb;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		array = new int[9][9];
		sb = new StringBuilder();

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

		Sudoku(0, 0);

	}

	static void Sudoku(int r, int c) {

		if (c == 9) {
			sb.append("\n");
			Sudoku(r + 1, 0);
			return;
		}

		if (r == 9) {
			for (int i = 0; i < 9; i++) {
				for (int j = 0; j < 9; j++) {
					System.out.print(array[i][j]);
				}
				System.out.println("");
			}
			System.exit(0);
		}

		if (array[r][c] == 0) {
			for (int i = 1; i <= 9; i++) {
				if (Possible(r, c, i)) {
					array[r][c] = i;
					Sudoku(r, c + 1);
				}
				array[r][c] = 0;
			}
		} else {
			Sudoku(r, c + 1);
		}
	}

	static boolean Possible(int r, int c, int value) {

		// 행
		for (int i = 0; i < 9; i++) {
			if (array[r][i] == value) {
				return false;
			}
		}

		// 열
		for (int i = 0; i < 9; i++) {
			if (array[i][c] == value) {
				return false;
			}
		}

		// 3*3
		int tempR = (r / 3) * 3;
		int tempC = (c / 3) * 3;

		for (int i = tempR; i < tempR + 3; i++) {
			for (int j = tempC; j < tempC + 3; j++) {
				if (array[i][j] == value) {
					return false;
				}
			}
		}

		return true;
	}

}

나중 풀이 : 백트래킹으로 구현했다.

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

public class Main {
	static int[][] array;
	static StringBuilder sb;

	public static void main(String[] args) throws Exception {
		SetData();
		dfs(0, 0);
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		array = new int[9][9];
		sb = new StringBuilder();

		for (int i = 0; i < 9; i++) {
			String s = br.readLine();
			for (int j = 0; j < 9; j++)
				array[i][j] = s.charAt(j) - '0';
		}
	}
	
	static void dfs(int r, int c) {

		if (c == 9) {
			dfs(r + 1, 0);
			return;
		}

		if (r == 9) {
			for (int i = 0; i < 9; i++) {
				for (int j = 0; j < 9; j++) {
					sb.append(array[i][j]);
				}
				sb.append("\n");
			}
			System.out.println(sb);
			System.exit(0);		// 이렇게 바로 끝내줘야지 시간초과가 나지 않음
		}

		if (array[r][c] == 0) {
			for (int i = 1; i <= 9; i++) {
				if (Sudoku(r, c, i)) {
					array[r][c] = i;
					dfs(r, c + 1);
				}
				array[r][c] = 0;
			}
		} else {
			dfs(r, c + 1);
		}
	}

	static boolean Sudoku(int r, int c, int value) {
		// 행
		for (int i = 0; i < 9; i++) {
			if (array[r][i] == value) {
				return false;
			}
		}

		// 열
		for (int i = 0; i < 9; i++) {
			if (array[i][c] == value) {
				return false;
			}
		}

		// 3*3
		int tempR = (r / 3) * 3;
		int tempC = (c / 3) * 3;

		for (int i = tempR; i < tempR + 3; i++) {
			for (int j = tempC; j < tempC + 3; j++) {
				if (array[i][j] == value) {
					return false;
				}
			}
		}

		return true;
	}
}