백준2667 단지번호 붙이기

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

2667번: 단지번호붙이기

 

전형적인 미로문제였다 DFS를 이용하여 문제를 해결하였다. 

두가지 방법을 이용해서 문제를 풀어보았다.

방법 1

import java.io.*;
import java.util.*;
 
public class Main {
    static int res;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] map = new int[n][n];
        boolean[][] visit = new boolean[n][n];
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            String[] in = br.readLine().split("");
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(in[j]);
            }
        }
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map.length; j++) {
                if(map[i][j]==1 && !visit[i][j]){
                    res= fun(i,j,map,visit);
                    list.add(res);
                }
            }
        }
        Collections.sort(list);
        System.out.println(list.size());
        for(int i:list)
            System.out.println(i);
    }
    static int fun(int x,int y,int[][] map , boolean[][] visit){
        if(x>=map.length||y>=map.length||x<0||y<0||map[x][y]==0||visit[x][y]){
            return 0;
        }
        visit[x][y] = true;
        return 1+fun(x+1,y,map,visit)+fun(x-1,y,map,visit)+fun(x,y+1,map,visit)+fun(x,y-1,map,visit);
    }
 
}
 

 

방법 2

import java.io.*;
import java.util.*;
 
public class Main {
    static int[] offset = {1, -1, 0, 0};
    static int[] offset2 = {0, 0, 1, -1};
    static int res;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] map = new int[n][n];
        boolean[][] visit = new boolean[n][n];
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            String[] in = br.readLine().split("");
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(in[j]);
            }
        }
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map.length; j++) {
                if(map[i][j]==1 && !visit[i][j]){
                    res = 1;
                    Maze(i,j,map,visit);
                    list.add(res);
                }
            }
        }
        Collections.sort(list);
        System.out.println(list.size());
        for(int i:list)
            System.out.println(i);
    }
    static int Maze(int x, int y, int[][] map, boolean[][] visit) {
        visit[x][y] = true;
        for (int i = 0; i < 4; i++) {
            int tx = x + offset[i];
            int ty = y + offset2[i];
            if (tx < map.length && ty < map.length && ty >= 0 && tx >= 0) {
 
                if (map[tx][ty] == 1 && !visit[tx][ty]) {
                    Maze(tx, ty, map, visit);
                    res++;
                }
            }
 
        }
        return res;
    }
}