[Java] 백준 바이러스 & 점프왕 쩰리 (Small)

2606 바이러스 문제 링크

#1

13분

import java.awt.*;
import java.io.*;
import java.util.*;
import java.util.List;

class Main {
    static boolean[] visited;
    static int N;
    static int[][] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        arr = new int[N+1][N+1];
        int a,b;
        StringTokenizer st;
        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            arr[a][b] = 1;
            arr[b][a] = 1;
        }

        visited = new boolean[N+1];
        dfs(1);
        int answer = -1;
        for(int i=1; i<=N; i++) {
            if(visited[i]) answer++;
        }

        bw.write(answer+"");
        bw.flush();
        bw.close();
    }

    static void dfs(int i) {
        if(!visited[i]) {
            visited[i] = true;
            for(int j=1; j<=N; j++) {
                if(arr[i][j] == 1) {
                    dfs(j);
                }
            }
        }
    }
}

• dfs 문제

16173 점프왕 쩰리 (Small) 문제 링크

#1

import java.awt.*;
import java.io.*;
import java.util.*;
import java.util.List;

class Main {
    static int N;
    static int[][] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

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

        boolean result = dfs(0, 0);
        String answer = result ? "HaruHaru" : "Hing";

        bw.write(answer);
        bw.flush();
        bw.close();
    }

    static boolean dfs(int x, int y) {
        if(arr[x][y] == -1) return true;

        boolean a = false;
        boolean b = false;
        if(inBorad(x + arr[x][y], y)) {
            a = dfs(x + arr[x][y], y); // 오른쪽
        }
        if(inBorad(x, y + arr[x][y])) {
            b = dfs(x, y + arr[x][y]); // 왼쪽
        }

        return a || b;
    }

    static boolean inBorad(int x, int y) {
        if(x>=0 && x<N && y>=0 && y<N) return true;
        else return false;
    }
}

• dfs 메모리 초과남

#2

import java.awt.*;
import java.io.*;
import java.util.*;
import java.util.List;

class Main {
    static int N;
    static int[][] arr;
    static boolean[][] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

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

        boolean result = dfs(0, 0);
        String answer = result ? "HaruHaru" : "Hing";

        bw.write(answer);
        bw.flush();
        bw.close();
    }

    static boolean dfs(int x, int y) {
        if(arr[x][y] == -1) return true;

        boolean a = false;
        boolean b = false;
        if(inBorad(x + arr[x][y], y) && !visited[x + arr[x][y]][y]) {
            visited[x + arr[x][y]][y] = true;
            a = dfs(x + arr[x][y], y); // 오른쪽
        }
        if(inBorad(x, y + arr[x][y]) && !visited[x][y + arr[x][y]]) {
            visited[x][y + arr[x][y]] = true;
            b = dfs(x, y + arr[x][y]); // 아래
        }

        return a || b;
    }

    static boolean inBorad(int x, int y) {
        if(x>=0 && x<N && y>=0 && y<N) return true;
        else return false;
    }
}

• 메모리 초과가 나면 값을 저장해서 재귀를 줄일 수 있는 법을 찾아야 되네
• 이게 오른쪽, 아래로만 이동해서 반복이 없는 줄 알았는데
• 겹치는 게 꽤 있을 수 있음