Karice의 여행 & 코딩 블로그

문제 설명

풀이

보자마자, DP, 와 BFS가 바로 생각났다. 그래서 바로 BFS로 풀었는데, 처음에는 visit을 해쉬맵(map)이 아닌 배열로 했다가 메모리 초과가 계속 떠서 더 찾아보니 HashMap으로 하면 더 빨라서 바로 바꾸었다.

그래도 계속해서 오답이 나오길래, Int에 문제가 있는 것 같아서 바로 Long으로 바꿔보니 통과했다.

역시 Input값의 범위도 항상 잘 봐야겠다.

코드

첫번째 코드 - 틀림

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int N,M;
    static int count;
    static int[] visit;

    public static void main(String[] args) throws IOException {
        // 1. 값 입력받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        visit = new int[M+1];
        count = 0;

        count = bfs();
        System.out.println(count);
    }

    private static int bfs() {
        Queue<int[]> que = new LinkedList<>();
        que.add(new int[] {N,0});
        visit[N] = 0;

        while (!que.isEmpty()) {
            int[] out = que.poll();

            if (out[0] == M) return out[1] + 2;
            if ( out[0] * 2 <= M && visit[out[0]*2] == 0 ){
                visit[out[0] * 2] = out[1]+1;
                que.add(new int[] {out[0] * 2,out[1]+1});
            }
            if ( out[0] * 10 + 1 <= M && visit[out[0] * 10 + 1] == 0 ){
                visit[out[0] * 10 + 1] = out[1]+1;
                que.add(new int[] {out[0] * 10 + 1,out[1]+1});
            }
        }
        return -1;
    }
}

완성된 코드 - 정답

import java.io.*;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int N,M;
    static long count;
    static HashMap<Long, Long> map = new HashMap<>();

    public static void main(String[] args) throws IOException {
        // 1. 값 입력받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        count = bfs();
        if(count == -1)
            System.out.println(count);
        else
            System.out.println(count+1);
    }

    private static long bfs() {
        Queue<long[]> que = new LinkedList<>();
        que.add(new long[] {N,0});

        while (!que.isEmpty()) {
            long[] out = que.poll();

            if (out[0] == M) return out[1];
            if ( out[0] * 2 <= M && !map.containsKey(out[0]*2)){
                map.put(out[0] * 2, out[1]+1);
                que.add(new long[] {out[0] * 2,out[1]+1});
            }
            if ( out[0] * 10 + 1 <= M && !map.containsKey(out[0] * 10 + 1) ){
                map.put(out[0] * 10 + 1, out[1]+1);
                que.add(new long[] {out[0] * 10 + 1,out[1]+1});
            }
        }
        return -1;
    }
}

문제 설명

풀이

수학적 해석을 이용한 문제라고 생각해서 머리를 굴려보았다.

알파벳 별로 (총 문자열길이 - 자릿수)를 알파벳 배열에 넣는다. 그러면 GCF는 각각 다음과 같이 들어간다.

G => alpha[6] = 100

C => alpha[2] = 10

F => alpha[5] = 1

이렇게 넣어서 내림차순으로 정렬한 뒤 9부터 차례대로 숫자를 대입해서 계산해주면 답이 나온다!!

코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        //testcase 및 문자열 입력
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String [] arr = new String[n];
        int [] alpha = new int[26];
        for(int i=0; i<n; i++){
            arr[i] = sc.next();
        }


        for(int i=0; i<n; i++){
            int temp = (int)Math.pow(10,arr[i].length()-1);
            for(int j=0; j<arr[i].length(); j++){
                alpha[(int)arr[i].charAt(j)-65]+=temp;
                temp /=10;
            }
        }

        Arrays.sort(alpha);
        int index = 9;
        int sum =0;
        for(int i=alpha.length-1; i>=0; i--){
            if(alpha[i] == 0){
                break;
            }
            sum+= alpha[i]*index;
            index--;
        }
        System.out.println(sum);
    }
}

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

문제 설명

풀이

미로탐색하는 것은 뭐다? 대부분 BFS로 모든 길을 탐색해봐야한다. 가끔 DFS나 백트래킹이 있지만 대부분 BFS로 먼저 해보는게 경험상 좋은 것 같다. BFS로 방향을 정하면 큰 문제가 없다.

매번 문제 풀듯이, queue에 넣어주고 visit체크해주고, 옮기면서 타당성 체크해주고 통과하면 다시 queue에 넣어준다. 결국 BFS, DFS 판별하는게 키포인트!!

DFS로도 해봤는데 시간 초과가 뜸!! 문제별로 속도차이가 꽤 있는 듯

코드

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int N,M;
    static int count;
    static int[][] map;
    static int[][] dis;
    static int[] dx = {0,1,0,-1};
    static int[] dy = {1,0,-1,0};

    public static void main(String[] args) throws IOException {
        // 1. 값 입력받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        count = 0;
        map = new int[N+1][M+1];
        dis = new int[N+1][M+1];

        Queue<int[]> que = new LinkedList<int[]>();

        for(int i =0; i< N; i++){
            String[] input = br.readLine().split("");
            for(int j =0; j<M; j++){
                map[i][j] = Integer.parseInt(input[j]);
            }
        }
//        for(int i =0; i< N; i++){
//            for(int j =0; j<M; j++){
//                System.out.print(map[i][j] + " ");
//            }
//            System.out.println();
//        }
        que.add(new int[] {0,0,0});
        dis[0][0] = 2;

        while (!que.isEmpty()) {
            int[] now =  que.poll();
            int x = now[0];
            int y = now[1];
            int cnt = now[2];
//            System.out.println("x축:"+y+" y축:"+x+" cnt:"+cnt);

            for(int z=0; z<4; z++){
                int cx = x + dx[z];
                int cy = y + dy[z];

                if(cx < 0 || cy < 0 || cx >= N || cy >= M || map[cx][cy] == 0 || dis[cx][cy] != 0){
                    continue;
                }
//                System.out.println("cx축:"+cy+" cy축:"+cx+" map:"+map[cx][cy]+" dis:"+dis[cx][cy]);
                dis[cx][cy] = 2;
                if (cx == N-1 && cy == M-1){
                    count = cnt+2;
                }
                que.add(new int[] {cx,cy,cnt+1});
            }
        }

        System.out.println(count);

    }
}

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

문제 설명

풀이

일단 DFS나 BFS 둘다 할 수 있다는 생각이 들었다. 하지만, 실제로 BFS를 통해 구현이 좋아보여서 그렇게 시작하게 되었다.

단순한 BFS 문제로, 갈수 있는 방향들을 계속 보내면서 queue에 넣고 도착지점에 도착할때까지 count를 증가시켜주면 된다. 

count를 인자로 계속 들고 있어야 되는게 핵심인듯

기초적인 BFS 문제!

코드

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class knight {
    int r;
    int c;
    int cnt;
    knight(int r, int c, int cnt){
        this.r = r;
        this.c = c;
        this.cnt = cnt;
    }
}


public class Main {
    static int N;
    static int[][] map;
    static boolean[][] visit;
    static int r1,c1,r2,c2;
    static int[] dr = {-2,-2,0,0,2,2};
    static int[] dc = {-1,1,-2,2,-1,1};



    public static void main(String[] args) throws IOException {
        // 1. 값 입력받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N+1][N+1];
        visit = new boolean[N+1][N+1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        r1 = Integer.parseInt(st.nextToken());
        c1 = Integer.parseInt(st.nextToken());
        r2 = Integer.parseInt(st.nextToken());
        c2 = Integer.parseInt(st.nextToken());

        bfs();
    }

    private static void bfs() {
        Queue<knight> que = new LinkedList<knight>();
        que.add(new knight(r1,c1,0));
        visit[r1][c1] = true;

        while(!que.isEmpty()){
            knight k = que.poll();

            for(int i =0; i<6; i++){
                int nr = k.r + dr[i];
                int nc = k.c + dc[i];

                if(nr <0 || nr > N || nc < 0 || nc > N || visit[nr][nc]){
                    continue;
                }
                if(nr == r2 && nc == c2){
                    System.out.println(k.cnt+1);
                    System.exit(0);
                }
                visit[nr][nc] = true;
                que.add(new knight(nr,nc,k.cnt+1));
            }
        }
        System.out.println(-1);
    }

}

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

문제 설명

풀이

모든 가지의 수를 구하는데 오름차순이라는 조건이 걸려있다.

그렇기에 일단 최심부까지 들어가는 DFS를 해야된다고 일단 생각이 났다.

그리고 백트래킹을 통해 각각의 경우의 수를 모두 파악하려고 하였다.

하지만 DFS 인자와 시작을 어떻게 해야할지 잘몰라서 방황하다가, start를 기준으로 계속 올라가게 만들면 된다는 생각을 했다. 그리고 for문은 dfs를 돌다가 마지막 조건에 도달했을때 해야된다는 것도 여기서 깨닫게 되었다.

백트래킹은 순차적으로 접근하여서 사전순으로 나열하기 좋음

코드

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int[] lis;
    static boolean[] visit;

    public static void main(String[] args) throws IOException {
        // 1. 값 입력받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while(true){
            String input = br.readLine();
            if(input.equals("0")){
                return;
            }
            StringTokenizer st = new StringTokenizer(input);
            N = Integer.parseInt(st.nextToken());
            lis = new int[N+1];
            visit = new boolean[N+1];
            for(int i =0; i<N; i++){
                lis[i] = Integer.parseInt(st.nextToken());
            }

            dfs(0,0); //DFS어떻게 시작하는지 확실하게 정리!!!
            System.out.println();
        }
    }

    private static void dfs(int start, int depth) {
        if(depth == 6){
            for (int i=0; i<N; i++){
                if(visit[i]){
                    System.out.print(lis[i] + " ");
                }
            }
            System.out.println();
        }
        else{ //이부분 중요!!!
            for(int i=start; i< N; i++){
                visit[i] = true;
                dfs(i+1,depth+1);
                visit[i] = false;
            }
        }
    }
}

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

문제 설명

풀이

일단 상어마다 모두 주변을 확인해서, 안전거리를 모두 구해야한다. 그렇게 생각하면 어떻게 모두 확인해볼지 생각해봐야 한다.

계속해서 안전거리를 추가해줘야하니 DFS나 BFS를 해줘야하는데, 끝까지 갈필요 없이, 최대한 인접한 곳을 보는 것이니 BFS로 하였다.

그리고 매우 기초적인 BFS라서 BFS의 흐름을 풀어보기에 좋은 문제였다.

코드

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int N,M;
    static int count;
    static int[][] map;
    static int[][] dis;
    static int[] dx = {-1,0,1,-1,1,-1,0,1};
    static int[] dy = {-1,-1,-1,0,0,1,1,1};

    public static void main(String[] args) throws IOException {
        // 1. 값 입력받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        count = 0;
        map = new int[N+1][M+1];
        dis = new int[N+1][M+1];

        Queue<int[]> que = new LinkedList<int[]>();

        for(int i =0; i< N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j =0; j<M; j++){
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j] == 1){
                    que.add(new int[] {i,j});
                }
            }
        }

        while (!que.isEmpty()) {
            int[] now =  que.poll();
            int x = now[0];
            int y = now[1];

            for(int z=0; z<8; z++){
                int cx = x + dx[z];
                int cy = y + dy[z];

                if(cx < 0 || cy < 0 || cx >= M || cy >= N || map[cx][cy] == 1 || dis[cx][cy] != 0){
                    continue;
                }

                dis[cx][cy] = dis[x][y] + 1;
                if (dis[cx][cy] > count){
                    count = dis[cx][cy];
                }
                que.add(new int[] {cx,cy});
            }
        }

        System.out.println(count);

    }
}

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

문제 설명

풀이

연결되어있는 선들의 연결요소를 구하는 문제였다.

생각해보면, 모든 선을 체크해보면서 같은 연결요소인지 체크를 해봐야하니 DFS나 BFS가 적합하다고 판단했다.

좀 더 생각해보면 DFS를 통해 연결요소를 모두 찾고 visit을 체크 해준 다음, 나머지 연결 안된 요소들을 또다시 DFS로 돌리면 된다는 것을 깨달을 수 있다.

그래서 DFS로 풀기 시작하는데, ArrayList안에 ArrayList를 넣는 형식으로 풀이하였다

ArrayList에 정점의 갯수만큼 ArrayList를 만들어주었다.

그리고 양방향으로 선을 모두 입력시켜주었다.

마지막으로 가장 바깥의 ArrayList를 돌면서 체크가 안되어있는 정점을 DFS로 돌린다. (+ 카운트도 추가해줌)

DFS에서는 정점과 연결된 정점들에 대한 For문을 돌리면서 다시 DFS를 돌리면 완성!!

중간에 visit을 체크해주면서 dfs를 돌리고 answer를 추가해주는게 핵심이다!!

깨닫게 된 점

• DFS 내부에서 visit = true를 설정해주어야 한다.
• visit를 1차원 배열로만 사용해도 되는데 너무 힘들게 생각했다.
• 점마다 visit안한 정점을 DFS로 돌리고, 연결된 것들을 함수내에서 다시 for문으로 실행시키면 된다.

코드

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    static int N,M;
    static ArrayList<ArrayList<Integer>> dots;
    static int count;
    static boolean[] visit;

    public static void main(String[] args) throws IOException {
        // 1. 값 입력받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        dots = new ArrayList<>();

        for(int i=1; i< N+2; i++){
            dots.add(new ArrayList<Integer>());
        }

        for(int i =0; i< M; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            dots.get(a).add(b);
            dots.get(b).add(a);
        }
        visit = new boolean[N+1];
        count = 0;

        for(int i=1; i < N+1; i++){
            if(!visit[i]){ //아직 체크가 안됐을 경우
                dfs(i);
                count++;
            }
        }
        System.out.println(count);
    }

    private static void dfs(int x) {
        if (visit[x]) return;
        else{
            visit[x] = true;
            for(int i : dots.get(x)){
                if(!visit[i]){
                    dfs(i);
                }
            }
        }
    }
}

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