<stdio.han>

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

[난이도]

- Silver 4

[알고리즘]

- bfs

[코드]

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

public class Main {
    static int R, C;
    static char[][] graph;
    static boolean[][] visited;
    static int[] dx = {-1, 1, 0, 0}; // 상, 하, 좌, 우
    static int[] dy = {0, 0, -1, 1}; // 상, 하, 좌, 우
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        graph = new char[R][C];
        visited = new boolean[R][C];
        int answer = 0;

        for (int i = 0; i < R; i++) {
            String input = br.readLine();
            for (int j = 0; j < C; j++) {
                graph[i][j] = input.charAt(j);
            }
        }
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (graph[i][j] == '#') { // if graph[i][j] is grass
                    if (!visited[i][j]) {
                        bfs(i, j);
                        answer++;
                    }
                }
            }
        }
        System.out.println(answer);
    }

    static void bfs(int r, int c) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{r, c});
        visited[r][c] = true;
        while (!queue.isEmpty()) {
            int[] tmp = queue.poll();
            int x = tmp[0];
            int y = tmp[1];
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx >= 0 && nx < R && ny >= 0 && ny < C) { // if 'nx' and 'ny' are inside of map
                    if (!visited[nx][ny]) { // and have never visited
                        if (graph[nx][ny] == '#') {
                            visited[nx][ny] = true; // turn visited[nx][ny] true
                            queue.add(new int[]{nx, ny}); // add queue
                        }
                    }
                }
            }
        }
    }
}

[풀이]

1. Using a double for loop, we check if graph[i][j] represents grass and has not been visited before. If so, we perform bfs(i, j).

2. Upon visiting, we mark the location as visited by setting it to true and explore adjacent grass patches using the 4-directional search logic.

3. Finally, we print the numbber of grass clumps.

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

[난이도]

- Silver 4

[알고리즘]

- bfs

[코드]

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

public class Main {
    static char[][] graph = new char[10][10];
    static boolean[][] visited = new boolean[10][10];
    static int[] dx = {-1, 1, 0, 0}; // 상, 하, 좌, 우
    static int[] dy = {0, 0, -1, 1}; // 상, 하, 좌, 우
    static Queue<int[]> queue = new LinkedList<>();
    static int answer = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));


        for (int i = 0; i < 10; i++) {
            String input = br.readLine();
            for (int j = 0; j < 10; j++) {
                graph[i][j] = input.charAt(j);
                if (graph[i][j] == 'L') {
                    queue.add(new int[]{i, j, 0});
                    visited[i][j] = true;
                }
            }
        }

        bfs();
        System.out.println(answer - 1); // B 제외하고 출력해줘야함


    }

    static void bfs() {
        while (!queue.isEmpty()) {
            int[] tmp = queue.poll();
            int x = tmp[0];
            int y = tmp[1];
            int cows = tmp[2];
            if (graph[x][y] == 'B') {
                answer = Math.min(answer, cows);
            }
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx >= 0 && nx < 10 && ny >= 0 && ny < 10) { // graph 내부안에서만 가능
                    if (!visited[nx][ny]) { // 방문하지 않은 지역
                        if (graph[nx][ny] != 'R') { // 돌이 있을 경우 돌아가야함
                            visited[nx][ny] = true; // 방문한곳으로 표시
                            queue.add(new int[]{nx, ny, cows + 1}); // 소의 개수를 1씩 늘림
                        }
                    }
                }
            }
        }
    }
}

[풀이]

Queue에 x와 y의 좌표뿐만아니라 소의 개수를 1씩 늘리면서 큐에담아주어야 B까지 도착했을 때의 소의 개수를 알 수가 있다.

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

[정답 코드]

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

public class Main {
    static int R, C, answer = Integer.MAX_VALUE;
    static char[][] graph;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static Queue<int[]> jihoon = new LinkedList<>(); // 지훈이의 좌표가 담긴 큐
    static Queue<int[]> fire = new LinkedList<>(); // 불의 좌표가 담긴 큐
    public static void main(String[] args) 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());
        graph = new char[R][C];
        for (int i = 0; i < R; i++) {
            String input = br.readLine();
            for (int j = 0; j < C; j++) {
                graph[i][j] = input.charAt(j);
                if (graph[i][j] == 'J') {
                    jihoon.offer(new int[]{i, j});
                }
                if (graph[i][j] == 'F') {
                    fire.offer(new int[]{i, j});
                }
            }
        }
        br.close();

        int answer = 0;
        while (true) {
            answer++; // while 반복문을 1회 시행할 때 마다 1분이 지난것이므로 1씩 증가
            int fireSize = fire.size(); // 불의 좌표가 담긴 큐의 크기 == 불의 갯수
            while (fireSize > 0) { // 번져야 할 불의 개수만큼만 반복, 이미 번진 불은 번지는것을 반복하지 않음
                fireSize--;
                int[] tmp = fire.poll();
                int x = tmp[0];
                int y = tmp[1];
                for (int i = 0; i < 4; i++) {
                    int nx = x + dx[i];
                    int ny = y + dy[i];
                    if (nx >= 0 && nx < R && ny >= 0 && ny < C) {
                        if (graph[nx][ny] == '.' || graph[nx][ny] == 'J') { // 불이 번진 위치가 벽이 아니라면
                            fire.offer(new int[]{nx, ny}); // 새로운 불의 좌표를 큐에 담는다
                            graph[nx][ny] = 'F'; // 번진만큼 지도를 갱신
                        }
                    }
                }
            }

            int jihoonSize = jihoon.size();
            while (jihoonSize > 0) { // 지훈이의 좌표가 담긴 큐가 비어있지 않을 경우
                jihoonSize--; // 새로운 지훈이의 좌표갯수만큼만 반복, 이미 이동한 지훈이는 이동하는것을 또 반복하지 않음
                int[] tmp = jihoon.poll();
                int x = tmp[0];
                int y = tmp[1];
                for (int i = 0; i < 4; i++) {
                    int nx = x + dx[i];
                    int ny = y + dy[i];
                    if (nx < 0 || nx >= R || ny < 0 || ny >= C) { // 탈출을 했을 경우
                        System.out.println(answer);
                        return;
                    }
                    if (graph[nx][ny] == '.') { // 이동가능한 자리일 경우
                        jihoon.offer(new int[]{nx, ny}); // 이동한 위치의 좌표를 큐에 담는다
                        graph[nx][ny] = 'J'; // 이동한 위치를 J로 갱신 (사실 이 코드는 필요하지는 않음)
                    }
                }
            }
            if (jihoon.isEmpty()) { // 새로이동할 때마다 지훈이의 좌표가 담긴 큐 jihoon 이 늘어나는데, 이동이 불가능하면 큐가 비게 됨
                System.out.println("IMPOSSIBLE");
                return;
            }
        }
    }
}

[설명]

bfs심화문제이다. 지훈이가 4방탐색을 하며 지도밖을 나갈 경우 반복문이 종료되는 것까지를 구현하는것은 약간만 생각하면 할 수 있다. 하지만 다른문제와 다른것은 지훈이가 4방탐색을함과 동시에 불도 4방으로 퍼져나간다는것을 생각해야 한다. 나는 이부분에서 막혀서 다른글을 참고했다. 

대략적인 풀이방식은 이렇다 : 

1. 불과 지훈이의 좌표를 각 큐에 담는다.

2. 불이 먼저 퍼져나가며 퍼져나간 불의 위치를 큐에 담는다.

3. 지훈이가 4방탐색을 하며 지훈이가 갈 수 있는 모든위치의 좌표를 큐에 담는다.

4. 이미 퍼져나간 불은 한 번더 퍼져나갈필요가없다. 새롭게 퍼져나간 불만 다시 퍼져나간다. (애초에 이미 퍼져나간불은 큐에 좌표가 없다.)

5. 3에서 4방탐색을 하며 지훈이가 갈 수 있는 모든 위치에서 다시 4방탐색을 하며 탈출구를 찾는다.

6. 4, 5를 반복한다.

7 - 1. 지훈이의 좌표가 지도 밖을 나갈경우 정답을 출력해준다.

7 - 2. 지훈이가 더이상 새롭게 이동할수 있는 위치가 없을 경우 jihoon 큐에는 더이상 값이 안담겨있기 때문에 IMPOSSIBLE을 출력해준다.

디버깅모드를 하고 지도의 모습을 시뮬레이션한것을 보면 약간은 신기하다. 여기서 중요한점은 불이 지훈이의 위치가 담긴 자리까지 불이 번져나가며 덮어버리는 경우가 있는데. 단순히 지도에서만 그렇고 지훈이의 좌표는 jihoon 큐 안에 담겨있기 때문에 문제없다.

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

[정답코드]

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

public class Main {
    static int[][] graph;
    static boolean[][] visited;
    static int[][] result;
    static int n, m;
    static int[] dx = {-1, 1, 0, 0}; // 상,하,좌,우
    static int[] dy = {0, 0, -1, 1};
    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 = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        graph = new int[n][m];
        visited = new boolean[n][m];
        result = new int[n][m];
        int x=0, y=0;

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < m; j++) {
                graph[i][j] = Integer.parseInt(st.nextToken());
                if (graph[i][j] == 2) {
                    x = i;
                    y = j;
                } else if (graph[i][j] == 0) {
                    visited[i][j] = true;
                }
            }
        }
        bfs(x, y);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visited[i][j]) {
                    result[i][j] = -1;
                }
                System.out.print(result[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void bfs(int x, int y) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{x, y});
        visited[x][y] = true;

        while (!queue.isEmpty()) {
            int tmp[] = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nx = tmp[0] + dx[i];
                int ny = tmp[1] + dy[i];
                if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                    if (!visited[nx][ny] && graph[nx][ny] == 1) {
                        visited[nx][ny] = true;
                        result[nx][ny] = result[tmp[0]][tmp[1]] + 1;
                        queue.add(new int[]{nx, ny});
                    }
                }
            }
        }
    }
}

[설명]

bfs를 활용해야하는 문제이다. 시작지점의 위치를 입력받고 입력받은 위치를 큐에 넣고 bfs로직을 돌려준다.

bfs로직은 입력받은 x, y 를 큐에 넣고  해당 위치를 기준으로 4방탐색을 한다. 4방탐색을 했을 때 방문하지않은장소이고, 갈 수 있는 장소이고, 지도 내에 있다면 visited를 true로 변경해주고, 새로 탐색한 위치의 값을 이동할 때 마다 1씩 증가시켜준다. 그리고 새로탐색한 위치를 큐에 넣어준다.

백준 7576번: 토마토[JAVA]

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

[정답 코드]

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; // 최소 날짜
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    static Queue<int[]> q = new LinkedList<>();

    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(), " ");


        M = Integer.parseInt(st.nextToken()); // 세로 칸  초기화
        N = Integer.parseInt(st.nextToken()); // 가로 칸 초기화

        // 그래프 초기화
        graph = new int[N][M];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < M; j++) {
                graph[i][j] = Integer.parseInt(st.nextToken());
                if (graph[i][j] == 1) { // 1일 경우 큐에 삽입
                    q.add(new int[]{i, j});
                }
            }
        }
        System.out.println(bfs());
    }

    public static int bfs() {
        while (!q.isEmpty()) { // 큐가 다 빌때까지 실행
            int[] tmp = q.poll();
            int x = tmp[0];
            int y = tmp[1];
            // 4방 탐색
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                //그래프 범위 안에 있을 경우
                if (nx >= 0 && ny >= 0 && nx < N && ny < M) {
                    if (graph[nx][ny] == 0) {
                        q.add(new int[]{nx, ny});
                        graph[nx][ny] = graph[x][y] + 1; // 새로 추가된 곳은 원래 있던 수 + 1
                        // 그 이유는 날짜를 세기 위해
                    }
                }
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (graph[i][j] == 0) { // 그래프안에 0 이 존재하면 답은 -1
                    return -1;
                }
                // 그래프의 날짜중에 가장 큰 수를 찾으면 그것이 최종날짜
                count = Math.max(count, graph[i][j]);
            }
        }

        // 저장될 때부터 모든 토마토가 익어익는상태라면
        if (count == 1) {
            return 0;
        } else { // 아닐 경우 최종날짜 - 1 출력
            return count-1;
        }
    }
}

[설명]

BFS, DFS 를 이용해 푸는 문제이다. BFS를 활용해 풀었다. 4방탐색을 해야하기 때문에 dx/ dy 기법을 활용했다.

입력할때 1을 입력받을때 큐에 집어넣는다. 입력이 끝난후 bfs함수를 호출해 큐에 들어있는 값들을 호출시키며 4방탐색을 한다.

백준 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함수를 실행한다.