[알고리즘] 백준 1012 유기농 배추 -dfs, bfs- 자바 코틀린

 

 

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

1012번: 유기농 배추

 

저번에 풀었던 단지번호붙이기와 유사했다.

다만 입력값이 이전에 비해 귀찮아진게 많았다.

그리고 가로세로 길이가 각각 [세로길이][가로길이] 를 거꾸로 하는 사소한 실수를 안해야 한다. 입력값을 y(가로) , x(세로) 순으로 줘서 실수할 수 도 있다.  즉 배열 크기 세팅에 주의해야한다.

 

 

풀이는 다음과 같이 BFS를 사용하여 해결했다.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    private static int[][] map;
    private static boolean[][] visited;
    private static int[] dx = {-1, 0, 1, 0};
    private static int[] dy = {0, -1, 0, 1};
    private static int snakeCountResult = 0; //전체 방의 개수

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int testCaseCount = sc.nextInt();
        for (int i = 0; i < testCaseCount; i++) {
            int M = sc.nextInt(); // 가로길이
            int N = sc.nextInt(); // 세로길이
            int K = sc.nextInt(); //배추 개수
            // index 에러 안나게 배열 생성
            map = new int[N + 2][M + 2];
            visited = new boolean[N + 2][M + 2];
            //배열값 세팅
            for (int k = 0; k < K; k++) {
                int Y = sc.nextInt() + 1;
                int X = sc.nextInt() + 1;
                map[X][Y] = 1;
            }

            //순차적 탐색
            snakeCountResult = 0;
            for (int n = 1; n < N + 1; n++) {
                for (int m = 1; m < M + 1; m++) {
                    if (map[n][m] == 1 && visited[n][m] == false) {
                        bfs(n, m);
                    }
                }
            }
            System.out.println(snakeCountResult);
        }
    }

    private static void bfs(int x, int y) {
        Queue<Point> queue = new LinkedList<>();
        queue.offer(new Point(x, y));
        visited[x][y] = true;
        snakeCountResult++;
        while (!queue.isEmpty()) {
            Point point = queue.poll();
            //동서남북 탐색
            for (int i = 0; i < 4; i++) {
                int x2 = point.x + dx[i];
                int y2 = point.y + dy[i];
                if (!(map[x2][y2] == 0 || visited[x2][y2] == true)) {
                    visited[x2][y2] = true;
                    queue.offer(new Point(x2, y2));
                }
            }
        }
    }

    static class Point {
        int x;
        int y;

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

 

 

금방 풀었는데 이상한 인텔리제이에서 입력값을 받을 때 버퍼문제인지 아직도 잘 모르겠지만 다음과 같이 엔터를 한번 더눌러야 다음 결과 값이 나오는(?) 이상한 에러가 발생했다.

그래서 sc.nextLine()도 여러 줄에 써보면서 실험도 해보고 디버깅도 해봤었는데 이상이 없었다. 

계속 이 에러를 고칠려고 삽질을 하다가 백준에 그냥 제출해봤는데 맞았다고 통과되었다.

 

다행이긴 하나 찝찝하다. (인텔리제이에서는 마지막에 엔터를 한번 더 눌러야 다음 답이나오고 백준은 통과라니...)

원인을 아시는분을 댓글로 알려주시면 감사하겠습니다.!!

 

 

[2020-09-17 복습]

[Java]

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int M = 0; //배추밭 가로길이
    static int K = 0; //배추가 심어져 있는 위치의 개수
    private static int[][] map;
    private static boolean[][] isVisited;
    private static int N = 0; //배추밭 세로길이
    private static int result = 0; //지렁이개수
    private static int[] dx = {-1, 0, 1, 0};
    private static int[] dy = {0, -1, 0, 1};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int t = 0; t < T; t++) {
            result = 0;
            M = sc.nextInt();
            N = sc.nextInt();
            map = new int[N + 2][M + 2];
            isVisited = new boolean[N + 2][M + 2];
            K = sc.nextInt();
            for (int i = 0; i < K; i++) {
                int y = sc.nextInt() + 1;
                int x = sc.nextInt() + 1;
                map[x][y] = 1;
            }
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= M; j++) {
                    if (!isVisited[i][j] && map[i][j] == 1) {
                        bfs(i, j);
                        result++;
                    }
                }
            }
            System.out.println(result);
        }
    }

    static void bfs(int x, int y) {
        Queue<Point> queue = new LinkedList<>();
        queue.offer(new Point(x, y));
        isVisited[x][y] = true;
        while (!queue.isEmpty()) {
            Point point = queue.poll();
            for (int i = 0; i < 4; i++) {
                int x2 = point.x + dx[i];
                int y2 = point.y + dy[i];
                if (map[x2][y2] == 1 && !isVisited[x2][y2]) {
                    isVisited[x2][y2] = true;
                    queue.offer(new Point(x2, y2));
                }
            }
        }
    }

    static class Point {
        int x;
        int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

}

 

 

[Kotlin]

import java.util.*

internal var M = 0 //배추밭 가로길이
internal var K = 0 //배추가 심어져 있는 위치의 개수
private var map: Array<IntArray>? = null
private var isVisited: Array<BooleanArray>? = null
private var N = 0 //배추밭 세로길이
private var result = 0 //지렁이개수
private val dx = intArrayOf(-1, 0, 1, 0)
private val dy = intArrayOf(0, -1, 0, 1)


fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val T = sc.nextInt()
    for (t in 0 until T) {
        result = 0
        M = sc.nextInt()
        N = sc.nextInt()
        map = Array(N + 2) { IntArray(M + 2) }
        isVisited = Array(N + 2) { BooleanArray(M + 2) }
        K = sc.nextInt()
        for (i in 0 until K) {
            val y = sc.nextInt() + 1
            val x = sc.nextInt() + 1
            map!![x][y] = 1
        }
        for (i in 1..N) {
            for (j in 1..M) {
                if (!isVisited!![i][j] && map!![i][j] == 1) {
                    bfs(i, j)
                    result++
                }
            }
        }
        println(result)
    }
}

fun bfs(x: Int, y: Int) {
    val queue = LinkedList<Point>()
    queue.offer(Point(x, y))
    isVisited!![x][y] = true
    while (!queue.isEmpty()) {
        val point = queue.poll()
        for (i in 0..3) {
            val x2 = point.x + dx[i]
            val y2 = point.y + dy[i]
            if (map!![x2][y2] == 1 && !isVisited!![x2][y2]) {
                isVisited!![x2][y2] = true
                queue.offer(Point(x2, y2))
            }
        }
    }
}

data class Point(var x: Int, var y: Int)