[알고리즘] 백준 2667 단지번호붙이기 -dfs, bfs- 코틀린 자바

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

2667번: 단지번호붙이기

 

 

백준 dfs, bfs 단게별 풀기에 있는 단지번호붙이기 문제를 풀어봤다.

 

난 bfs를 사용하였다.

 

동서남북을 탐색하기 위해 다음과 같은 배열을 선언하여 (좌,우) (하, 상) 

private static int[] dx = {-1, 0, 1, 0};
    private static int[] dy = {0, -1, 0, 1};

 

 

 

다음과 같이 4번의 반복문을 돌려 현재 좌표기준으로 동서남북 탐색을 할 수 있다는 점을 알게 되었다. 

//동서남북 탐색
            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;
                    numOfHouse++;
                    queue.offer(new Point(x2, y2));
                }
            }

 

 

 

 

그리고 이차원배열에서 동서남북을 탐색할때 현재좌표가 [0][0] 이라든가 [max][max] 인 경우 배열범위를 벗어나 인덱스 에러가 뜰 수 있으므로 배열을 넉넉히 두칸정도 더 늘려주어 생성해주고 값을 [1][1]부터 담게 했다.

// index 에러 안나게 배열 생성
        map = new int[size + 2][size + 2];
        visited = new boolean[size + 2][size + 2];
        sc.nextLine();

        //배열 초기화
        for (int i = 1; i < size + 1; i++) {
            String str = sc.nextLine();
            for (int j = 1; j < size + 1; j++) {
                map[i][j] = str.charAt(j - 1) - '0';
            }
        }

 

 

 

전체 풀이코드는 다음과 같다.

정답을 맞추긴 했지만 뭔가 비효율적이고 용량을 차지하는 코드가 많은 것 같기도 하다. 

import java.util.*;

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 ArrayList<Integer> result = new ArrayList<Integer>();
    private static int totalNumOfHouse = 0; //전체 방의 개수

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int size = sc.nextInt();
        // index 에러 안나게 배열 생성
        map = new int[size + 2][size + 2];
        visited = new boolean[size + 2][size + 2];
        sc.nextLine();

        //배열 초기화
        for (int i = 1; i < size + 1; i++) {
            String str = sc.nextLine();
            for (int j = 1; j < size + 1; j++) {
                map[i][j] = str.charAt(j - 1) - '0';
            }
        }

        //모든 배열 인덱스 시작점으로 탐색
        for (int i = 1; i < size + 1; i++) {
            for (int j = 1; j < size + 1; j++) {
                if (map[i][j] == 1 && visited[i][j] == false) {
                    bfs(i, j);
                }
            }
        }

        System.out.println(totalNumOfHouse);
        Collections.sort(result);
        for (int num : result) {
            System.out.println(num);
        }

    }

    private static void bfs(int x, int y) {
        int numOfHouse = 0;
        Queue<Point> queue = new LinkedList<>();
        queue.offer(new Point(x, y));
        visited[x][y] = true;
        totalNumOfHouse++;
        numOfHouse++;
        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;
                    numOfHouse++;
                    queue.offer(new Point(x2, y2));
                }
            }
        }
        result.add(numOfHouse);
    }

    static class Point {
        int x;
        int y;

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

 

 

 

P.S

혹시 나중에 까먹을까봐 남긴다.

7
0110100
0110101
1110101
0000111
0100000
0111110
0111000

테스트케이스가 위와 같은데 

스캐너로 nextInt()로 7을 부르고 다음줄을 다 부를려면은 nextLine() 할텐데 이 때 바로 nextLine을 하면 안불러와진다. (버퍼문제)

그래서 nextLine으로 처음에 첫줄의 버퍼를 지워주고 한번더 nextLine()을 통해 다음줄을 불러올수있다.

 int size = sc.nextInt();
        // index 에러 안나게 배열 생성
        map = new int[size + 2][size + 2];
        visited = new boolean[size + 2][size + 2];
        sc.nextLine();

        //배열 초기화
        for (int i = 1; i < size + 1; i++) {
            String str = sc.nextLine();
            for (int j = 1; j < size + 1; j++) {
                map[i][j] = str.charAt(j - 1) - '0';
            }
        }

 

 

 

 

 

 

 

[2020-09-17 복습]

[Java]

import java.util.*;

public class Main {
    static int[][] map;
    static boolean[][] isVisited;
    static int N = 0; //정사각형 크기
    static int totalNumOfHouse = 0;
    static ArrayList<Integer> result = new ArrayList();
    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);
        N = sc.nextInt();
        map = new int[N + 2][N + 2];
        isVisited = new boolean[N + 2][N + 2];
        for (int i = 1; i <= N; i++) {
            String line = sc.next();
            for (int j = 1; j <= N; j++) {
                map[i][j] = line.charAt(j-1) - '0';
            }
        }

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (!isVisited[i][j] && map[i][j] == 1)
                    bfs(i, j);
            }
        }
        System.out.println(totalNumOfHouse);
        Collections.sort(result);
        for (int i : result) {
            System.out.println(i);
        }
    }

    static void bfs(int x, int y) {
        int size = 1;
        Queue<Point> queue = new LinkedList<>();
        queue.offer(new Point(x, y));
        isVisited[x][y] = true;
        totalNumOfHouse++;
        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;
                    size++;
                    queue.offer(new Point(x2, y2));
                }
            }
        }
        result.add(size);
    }

    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 map: Array<IntArray> = emptyArray()
internal var isVisited: Array<BooleanArray> = emptyArray()
internal var N = 0 //정사각형 크기
internal var totalNumOfHouse = 0
internal var result: ArrayList<Int> = ArrayList()
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`)
    N = sc.nextInt()
    map = Array(N + 2) { IntArray(N + 2) }
    isVisited = Array(N + 2) { BooleanArray(N + 2) }
    for (i in 1..N) {
        val line = sc.next()
        for (j in 1..N) {
            map[i][j] = line[j - 1] - '0'
        }
    }

    for (i in 1..N) {
        for (j in 1..N) {
            if (!isVisited[i][j] && map[i][j] == 1)
                bfs(i, j)
        }
    }
    println(totalNumOfHouse)
    result.sort()
    for (i in result) {
        println(i)
    }
}

internal fun bfs(x: Int, y: Int) {
    var size = 1
    val queue = LinkedList<Point>()
    queue.offer(Point(x, y))
    isVisited[x][y] = true
    totalNumOfHouse++
    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
                size++
                queue.offer(Point(x2, y2))
            }
        }
    }
    result.add(size)
}

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