<stdio.han>

백준 4963번: 섬의 개수[JAVA]

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

[정답 코드]

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

public class Main {
    static int N; // 정점의 개수
    static int M; // 간선의 개수
    static int[][] graph; // 그래프배열
    static boolean[] visited; //방문한 자리
    static int count = 0; // 연결요소의 개수
    public static void main(String[] args) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        graph = new int[N][N];
        visited = new boolean[N];

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int u = Integer.parseInt(st.nextToken()) - 1; // 편하게 하기위해 -1
            int v = Integer.parseInt(st.nextToken()) - 1;
            graph[u][v] = 1;
            graph[v][u] = 1;
        }


        for (int i = 0; i < N; i++) {
            if (!visited[i]) { //방문하지 않은 자리라면 bfs함수 실행 후 count++;
                bfs(i);
                count++;
            }
        }
        System.out.println(count);
    }

    public static void bfs(int start) {
        Queue<Integer> q = new LinkedList<>(); // 큐 선언
        q.offer(start); //큐에 삽입
        visited[start] = true; //방문한곳 표시

        // 해당 기준으로 연결된 지점을 확인
        while (!q.isEmpty()) {
            int tmp = q.poll();
            for (int i = 0; i < N; i++) {
                if (graph[tmp][i] == 1 && !visited[i]) {
                    q.offer(i);
                    visited[i] = true;
                }
            }
        }
    }
}

[설명]

bfs 문제로 방향없는 그래프를 그린 후 조건에 해당하는 노드를 만나면 bfs 함수를 실행해 인접노드를 찾는다. 방문한 노드는 true 로 만들며 인접한노드이며 방문하지 않은 노드를 계속 찾는다. 탐색이 끝나면 count 를 1 증가시킨다. N번 노드 까지 탐색이 끝나면 출력한다.

백준 4963번: 섬의 개수[JAVA]

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

[정답코드]

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

public class Main {
    static int w;
    static int h;
    static int[][] map;
    static int[] dx = {0, 0, 1, -1, -1, 1, -1, 1};
    static int[] dy = {1, -1, 0, 0, -1, 1, 1, -1};
    static boolean[][] visit;
    static int count; // 섬의 개수
    public static void main(String[] args) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        while (true) { // w와 h가 0이 되면 종료
            st = new StringTokenizer(br.readLine(), " ");

            // w 지도의 너비, h 지도의 높이
            w = Integer.parseInt(st.nextToken());
            h = Integer.parseInt(st.nextToken());

            // 0이 되면 종료
            if (w == 0 && h == 0) {
                break;
            }

            //지도 배열 선언
            map = new int[h][w];
            //방문한 곳 배열 선언
            visit = new boolean[h][w];
            //지도 입력
            for (int i = 0; i < h; i++) {
                st = new StringTokenizer(br.readLine(), " ");
                for (int j = 0; j < w; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            count = 0;


            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    if (map[i][j] == 1 && !visit[i][j]) { // 섬이 있고 방문하지 않았다면 bfs 함수실행
                        bfs(i, j);
                        count++;
                    }
                }
            }
            System.out.println(count);
        }
    }

    public static void bfs(int x, int y) {
        visit[x][y] = true;

        //8방탐색
        for (int i = 0; i < 8; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            //지도범위 안에 있을 경우
            if (nx >= 0 && ny >= 0 && nx < h && ny < w) {
                if (map[nx][ny] == 1 && !visit[nx][ny]) { //8방탐색한곳이 방문하지않고, 섬이 존재할경우
                    bfs(nx, ny);
                }
            }
        }
    }
}

[설명]

지도를 설정한 후 지도의 시작지점부터 탐색을 시작한다. 섬이있는 자리 이면서 visit가 false 일경우 bfs 함수를 실행한다.

bfs 함수는 섬이있는 자리이면서 visit가 false 인 자리를 기준으로 8방 탐색을 실행한다. 8방 탐색을 실행할때 탐색한자리에 에 또 섬이있고 방문한적이 없는 자리면 그 자리를 기준으로 다시 bfs함수를 실행한다. 

백준 14888번: 연산자 끼워넣기[JAVA]

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

[정답 코드]

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main {
    static int MAX = Integer.MIN_VALUE;
    static int MIN = Integer.MAX_VALUE;
    static int N; // 숫자 개수
    static int[] arr; // 숫자 배열
    static int[] op = new int[4]; // 연산자 배열
    public static void main(String[] args) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        // 숫자 갯수 입력
        N = Integer.parseInt(st.nextToken());

        // 숫자 배열 입력
        arr = new int[N];
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        // 연산자 갯수 입력
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < 4; i++) {
            op[i] = Integer.parseInt(st.nextToken());
        }

        backTracking(arr[0], 1);

        //최대값 최소값 출력
        bw.write(MAX + "\n" + MIN);

        bw.flush();
        bw.close();
        br.close();
    }

    // 로직
    public static void backTracking(int num, int idx) {

        // idx == N 이 되면 종료, arr 끝까지 탐색했다는 의미
        if (idx == N) {
            MAX = Math.max(MAX, num);
            MIN = Math.min(MIN, num);
            return;
        }

        for (int i = 0; i < 4; i++) {
            // 해당 연산자가 존재하면, 해당연산자 사용한 후 개수 하나 제거
            if (op[i] > 0) {
                op[i]--;
                switch (i) {
                    case 0:	backTracking(num + arr[idx], idx + 1);	break;
                    case 1:	backTracking(num - arr[idx], idx + 1);	break;
                    case 2:	backTracking(num * arr[idx], idx + 1);	break;
                    case 3:	backTracking(num / arr[idx], idx + 1);	break;
                }
                // 재귀호출이 종료되면 다시 해당 연산자 개수를 복구한다.
                op[i]++;
            }
        }
    }
}

[정리]

그림의 예가 약간 잘못된것같고 이상하지만 참고하고 보자. 그림을 예로 들어보자면 입력값이 첫째 줄에 3, 둘째 줄에 2 3 4 셋째 줄에 1 1 1 1을 입력받았을 경우의 대략적인 그림이다. 첫번째 숫자부터시작해 2 + 3 - 4 순서대로 계산을 하고 그 다음은 2 + 3 * 4, 그 다음은 2 + 3 / 4 순서대로 진행하게 된다. 숫자가 더 많거나 연산자가 더 많을 경우에도 그림과 같이 진행된다고 보면 된다.

[느낀점]

아직 하노이 알고리즘도 그렇고, dfs, bfs 등 어려운 알고리즘은 혼자만의 생각으로는 아직 풀 수 없는것같다. 다른 글을 참고해가며 정말 어려울 경우에는 클론코딩을 해가며 풀게된다. 중요한 점은 그냥 참고하고 끝나는게 아니라 문제를 풀 때 만큼은 그림으로 그려가며 완벽하게 이해하는게 중요한것 같다.

백준 1914번: 하노이 탑[JAVA]

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

[정답 코드]

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int N = 0;

    public static void main(String[] args) throws Exception {

        // 원판의 개수 입력
        N = Integer.parseInt(br.readLine());

        //관계식
        System.out.println(BigInteger.TWO.pow(N).subtract(BigInteger.ONE));

        // N이 20 이하일 경우 과정 출력
        if (N <= 20) {
            hanoi(N, 1, 2, 3);
        }

        bw.flush();
        bw.close();
        br.close();
    }

    // [로직] n 옮길 원판, from 시작 기둥, tmp 거쳐갈 기둥, to 도착 기둥
    public static void hanoi(int n, int from, int tmp, int to) throws IOException{

        // n == 1 일경우 바로 이동
        if (n == 1) {
            bw.write(from + " " + to + "\n"); // 이동
            return;
        }

        hanoi(n - 1, from, to, tmp);
        bw.write(from + " " + to + "\n"); // 이동

        hanoi(n-1, tmp, from, to);
    }
}

[시행착오]

그림판으로 그림까지 그려가며 하노이 탑을 공부하고 이해하려 노력했다. 코드는 다른글을 참고했지만 이해하기는했다.

처음엔 메모리초과가 발생했다. 알아본 결과 수가 너무 커질 경우 메모리 초과가 발생해 count 를 int 에서 long 으로 변경했다. 그런데 이번엔 시간초과가 발생했다. long 도 문제였다. 한 번 움직일 때마다 count 를 1씩 늘려주는 방식은 N이 매우 큰수가 될때 시간을 많이 잡아먹어 효율이 안좋았다. 애초에 시작할때 움직일만큼의 방정식을 계산해 출력을 해주는것이좋다. 그리고 그때의 타입은 BigInteger가 되어야만 했다. int, long 둘다 N이 100일 경우 메모리를 초과하기 때문이다.

N 이 20이상일 경우에는 hanoi() 자체가 실행되는순간 시간과 메모리를 많이 차지하기때문에 20 이하일 경우에만 hanoi()를 실행하게했다.

[정리]

원판의 개수 N을 입력받는다.

그 N을 이용해 관계식을 도출해 원판이 움직이는 횟수를 출력한다.

N이 20 이하일 경우 hanoi()를 실행한다.

[하노이 알고리즘]

그림과 hanoi() 를 같이 보면 이해하기 쉽다.

N개의 원판이 1번기둥에 있다. 제일 아래 큰 원판이 N 번째 원판이다.

hanoi(N, from, tmp, to) 실행

1단계 : N번째 원판을 옮기기 위해서는 N번째 원판을 제외한 N-1 번째부터 1번째 원판까지를 2번 기둥으로 옮긴다.

hanoi(N-1, from, to, tmp)

2단계 : N번째 원판을 3번 기둥으로 옮긴다.

이동

3단계 : N-1 번째부터 1번째 원판을 3번기둥으로 옮긴다.

hanoi(N-1, tmp, from, to)

이렇게 간단하게 3단계로 구성되어있다. 직접 알고리즘을 짜려면 어렵지만 막상 알고나면 생각보다 어렵지 않다.

백준 17609번: 회문[JAVA]

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

[정답 코드]

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        // 문자열의 개수를 나타내는 정수 T
        int T = Integer.parseInt(st.nextToken());
        // 문자열을담는 배열
        String[] arr = new String[T];
        String str = "";

        //문자열 입력받은 후 배열에 저장
        for (int i = 0; i < T; i++) {
            str = br.readLine();
            System.out.println(palindrome(0, str.length()- 1, str, 0));
        }
    }

    // 로직
    private static int palindrome(int start, int end, String s, int check) {
        // 문자 삭제를 2번이상 할 경우 바로 2를 반환
        if (check >= 2) {
            return 2;
        }

        // start 포인터와 end 포인터가 만나거나 지나치기 전까지 반복
        while (start < end) {
						// 같을 경우 포인터 한칸 진행
            if (s.charAt(start) == s.charAt(end)) {
                start++;
                end--;
            } else {
                // ex) abbab 같은 경우 두 경우를 비교해 더 작은 수를 반환
                return Math.min(palindrome(start + 1, end, s, check + 1), palindrome(start, end - 1, s, check + 1));
            }
        }
        return check;
    }
}

[정리]

투 포인터 알고리즘과 재귀함수를 활용해 풀었다. 처음엔 재귀함수 없이 while 문과 for 문으로 해결하려고 했지만 반례를 발견할 때 마다 코드가 한줄 한줄 추가되더니 스파게티 코드가 되었다. 몇시간 동안 수정 후 반례 abbab 를 만났을 때 왼쪽 문자를 제거했을 경우와 오른쪽 문자를 제거했을 경우 두 가지 모두를 생각해야 한다는 걸 깨닫고 수정하려 했지만 이미 코드는 난장판이 되어있었다. 그래서 싹 다 지우고 혼자 해결하는것을 포기하고 구글링을하며 반정도 클론코딩을 하며 해결했다. 4시간 정도 걸려서 풀었지만 막상 풀고나니 처음 시작을 제대로 했더라면 금방 풀수있는 문제였다.

백준 15961번: 회전 초밥[JAVA]

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

[정답 코드]

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");

        // N=접시의 수, d=초밥의 가짓수, k=연속해서 먹는 접시의 수, c=쿠폰 번호
        int N = Integer.parseInt(st.nextToken());
        int d = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());

        // 회전 초밥 배열
        int[] dishes = new int[N];
        for(int i=0;i<N;i++){
            dishes[i] = Integer.parseInt(br.readLine());
        }

        //먹은 초밥 배열 먹으면 1, 안먹으면 0
        int[] eat = new int[d+1];

        // 0번부터 k개 먹었을 경우 상태
        int cnt = 0;
        for(int i=0;i<k;i++){
            if(eat[dishes[i]] == 0) {
                cnt++;
            }
            eat[dishes[i]]++;
        }

        // 먹을 수 있는 초밥의 가짓수의 최댓값, 기본 값은 0번부터 k개 먹었을 경우의 최대값
        int max = cnt;

        //투포인터 초기화
        int start = 1;
        int end = k;

        //로직
        while(true){
            if(eat[dishes[start-1]] == 1) { // start-1 초밥이 이미 먹은 초밥이라면 cnt--
                cnt--;
            }
            // else 아니라면 그대로
            //먹은 초밥 배열 --
            eat[dishes[start-1]]--;

            //새로운 초밥이 먹은 초밥이라면 cnt++
            if(eat[dishes[end]] == 0) {
                cnt++;
            }
            // else 아니라면 그대로
            //새로 먹은 초밥 배열 ++
            eat[dishes[end]]++;

            if(eat[c] == 0) { //쿠폰초밥을 안먹었다면 max, cnt+1 중 큰 수
                max = Math.max(max, cnt+1);
            } else { //쿠폰초밥을 이미 먹었다면 그냥 비교
                max = Math.max(max, cnt);
            }

            start++;
            end++;
            if(end==N) { //end포인터가 배열끝까지 갔을 경우 처음으로
                end = 0;
            }
            if(start==N) { //start 포인터가 배열 끝까지 갔을 경우 종료
                break;
            }
        }
        System.out.println(max);

        bw.flush();
        bw.close();
        br.close();
    }
}

[정리]

투 포인터 알고리즘을 이용해 푸는 문제이다. 시작지점과 끝지점 포인터를 만들어 창문이 움직이듯이 정해진 범위를 이동해 가며 푸는 문제이다. 슬라이딩 윈도우 알고리즘이라고도 부른다.

백준 2531번과 N의 범위를 제외하고 똑같은 문제이다. 이유는 모르겠지만 2531번 문제에서는 96%에서 실패가 나온다...