[20일 차] 알고리즘 (문제 풀기2)

---

25/02/21 (금)

와 벌써 금요일입니다.

오늘은 워크샵 발표도 없어서 기분이 좋습니다.

사실 제가 발표할 차례인데 안해서 좋습니다.

내일은 주말이라 또 너무 기분이 좋습니다!!

---

1.  실습

1) 백준

https://www.acmicpc.net/problem/17471 (미해결)

https://www.acmicpc.net/problem/17070 (해결)

유연근무제 : https://school.programmers.co.kr/learn/courses/30/lessons/388351 (해결)

비밀 코드 해독 : https://school.programmers.co.kr/learn/courses/30/lessons/388352 (때려침)

멍청함 셀프인증

지게차와 크레인 : https://school.programmers.co.kr/learn/courses/30/lessons/388353

 

2) G3_17471_게리맨더링

package bj;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;
// 전체 구역을 2개의 선거구 < = 부분집합 <= select[] 에 선택, 비선택을 true, false 로 기록 <= 두 개의 선거구는 선택된 구역, 비선택된 구역 나눈 개념
// 그래프 이므로 나뉘어진 선거구 내의 구역이 모두 연결 여부 
//    <= 각 선거구의 임의의 한 구역부터 출발 모든 구역에 갈 수 있는 지 완탐 (bfs, dfs)
//    <= 완탐을 통해 visit 배열 1개에 갈 수 있는 곳을 모두 기록 
//    <= 완탐 이후 visit 배열 확인 
// 모두 연결되어 있다면 인구수의 차를 계산, min 처리
// dfs
public class G3_17471_게리맨더링_풀이 {
    static int N, min;
    static int[][] matrix; // i, j 정점번호는 아니다.
    static boolean[] select; // 부분집합 처리용도
    static boolean[] visit; // 모든 구역이 연결되어 있는 지 확인 용도

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

        matrix = new int[N + 1][N + 1]; // 어차피 맨 앞이 더미 <= 그 자리에 인구수를 저장
        select = new boolean[N + 1];
        visit = new boolean[N + 1];

        // 인구수
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            matrix[i][0] = Integer.parseInt(st.nextToken());
        }

        // 정점별 연결
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken()); // 인접한 정점 수
            for (int j = 1; j <= n; j++) {
                int v = Integer.parseInt(st.nextToken());
                matrix[i][j] = v;  // matrix[i][v] = true 와 비교
            }
        }

        // 풒이
        min = Integer.MAX_VALUE;

        subset(1);

        if( min == Integer.MAX_VALUE ) System.out.println(-1);
        else System.out.println(min);
    }
    static void subset(int srcIdx) {
        // 기저조건
        if( srcIdx == N + 1 ) {
            // 부분집합 경우의 수 1개 완성 <= select 배열에 true, false 기록
            check();
            return;
        }

        select[srcIdx] = true;
        subset(srcIdx + 1);
        select[srcIdx] = false;
        subset(srcIdx + 1);
    }

    // v 정점에서 갈 수 있는 다른 정점 방문 visit에 기록
    static void dfs(int v, boolean sel) {
        visit[v] = true;

        for (int i = 1; i <= N; i++) {
            int adj = matrix[v][i];
            if( adj == 0 || visit[adj] || select[adj] != sel ) continue;

            dfs( adj, sel );
        }
    }


    // 나뉘어진 2 개 선거구가 유효 ( 적어도 1개 이상, 다 연결 )
    // 유효하다면 두 선거구의 인구수를 계산, 차이의 최소값 처리 
    static void check() {
        // visit 배열을 이용해서 연결여부 확인
        Arrays.fill(visit, false);

        // A 선거구 ( select 배열 true 인 구역 )
        // 선거구에 속한 구역 1개를 선택 완탐 진행 => 갈 수 있는 곳에 visit 기록
        int a = -1;
        for (int i = 1; i <= N; i++) {
            if( select[i] ) {
                a = i;
                break;
            }
        }

        if( a == -1 ) return; // A 선거구의 구역이 0

        dfs( a, true );

        // B 선거구 ( select 배열 false 인 구역 )
        // 선거구에 속한 구역 1개를 선택 완탐 진행 => 갈 수 있는 곳에 visit 기록
        int b = -1;
        for (int i = 1; i <= N; i++) {
            if( ! select[i] ) {
                b = i;
                break;
            }
        }

        if( b == -1 ) return; // B 선거구의 구역이 0

        dfs( b, false );

        // 두 선거구 모두 연결 확인
        for (int i = 1; i <= N; i++) {
            if( ! visit[i] ) return; // 어떤 선거구의 구역이 연결 X
        }

        // A, B 선거구의 인구수를 계산, 최소값 갱신
        int sumA = 0;
        int sumB = 0;

        for (int i = 1; i <= N; i++) {
            if( select[i] ) sumA += matrix[i][0];
            else sumB += matrix[i][0];
        }

        min = Math.min(min, Math.abs(sumA - sumB));
    }
}

• 구현 다하고 테케도 전부 맞았는데 틀렸다..

 

3) G5_17070_파이프 옮기기 1

package basic.Ch23_문제풀기2;

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

public class G5_17070_파이프옮기기1 {
    static int N, result;
    static int[][] arr;

    static int[] w_dy = {0,1, 0,0};
    static int[] w_dx = {1,1, 1,1};
    static int[] h_dy = {1,1, 1,1};
    static int[] h_dx = {0,1, 0,0};
    static int[] d_dy = {0,1,1, 1,1,1};
    static int[] d_dx = {1,0,1, 1,1,1};

    public static void main(String[] args) throws IOException {
        //입력
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N][N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine()," ");
            for (int j = 0; j < N; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        move(0,1, 0, 0);
        System.out.println(result);
    }

    public static void move(int hy, int hx, int ty, int tx){
        if(hy == N-1 && hx == N-1) {
            result++;
            return;
        }

        //가로
        if(ty == hy && tx+1 == hx){
            int hdy, hdx, tdy, tdx;
            for (int i = 0; i < 2; i++) {
                hdy = hy + w_dy[i];
                hdx = hx + w_dx[i];
                tdy = ty + w_dy[i+2];
                tdx = tx + w_dx[i+2];

                if(hdy>=0 && hdy<N && hdx>=0 && hdx<N && tdy>=0 && tdy<N && tdx>=0 && tdx<N){
                    if(i == 1) {
                        if(arr[hdy][hdx] != 1 && arr[tdy][tdx] != 1 && arr[hdy-1][hdx] != 1 && arr[hdy][hdx-1] != 1){
                            move(hdy, hdx, tdy, tdx);
                        }
                    }else if(arr[hdy][hdx] != 1 && arr[tdy][tdx] != 1){
                        move(hdy, hdx, tdy, tdx);
                    }
                }
            }
        }

        //세로
        if(ty+1 == hy && tx == hx){
            int hdy, hdx, tdy, tdx;
            for (int i = 0; i < 2; i++) {
                hdy = hy + h_dy[i];
                hdx = hx + h_dx[i];
                tdy = ty + h_dy[i+2];
                tdx = tx + h_dx[i+2];

                if(hdy>=0 && hdy<N && hdx>=0 && hdx<N && tdy>=0 && tdy<N && tdx>=0 && tdx<N){
                    if(i == 1) {
                        if(arr[hdy][hdx] != 1 && arr[tdy][tdx] != 1 && arr[hdy-1][hdx] != 1 && arr[hdy][hdx-1] != 1){
                            move(hdy, hdx, tdy, tdx);
                        }
                    }else if(arr[hdy][hdx] != 1 && arr[tdy][tdx] != 1){
                        move(hdy, hdx, tdy, tdx);
                    }
                }
            }
        }

        //대각
        if(ty+1 == hy && tx+1 == hx){
            int hdy, hdx, tdy, tdx;
            for (int i = 0; i < 3; i++) {
                hdy = hy + d_dy[i];
                hdx = hx + d_dx[i];
                tdy = ty + d_dy[i+3];
                tdx = tx + d_dx[i+3];

                if(hdy>=0 && hdy<N && hdx>=0 && hdx<N && tdy>=0 && tdy<N && tdx>=0 && tdx<N){
                    if(i == 2) {
                        if(arr[hdy][hdx] != 1 && arr[tdy][tdx] != 1 && arr[hdy-1][hdx] != 1 && arr[hdy][hdx-1] != 1){
                            move(hdy, hdx, tdy, tdx);
                        }
                    }else if(arr[hdy][hdx] != 1 && arr[tdy][tdx] != 1){
                        move(hdy, hdx, tdy, tdx);
                    }
                }
            }
        }
    }
}

• 블로그 gpt 안쓰고 푼 첫 골드문제 캬~