๐Ÿ“œ ์ฝ”๋”ฉํ…Œ์ŠคํŠธ/BAEKJOON\BFS, DFS

๋ฐฑ์ค€ 1926๋ฒˆ : ๊ทธ๋ฆผ (JAVA) ๋ฌธ์ œ ํ’€์ด

2021. 6. 23. 22:57
๋ชฉ์ฐจ
  1. โœ๏ธ ๋ฌธ์ œ
  2. ๐Ÿ” ๋ฌธ์ œ ํ•ด๊ฒฐ
  3. ๐Ÿ“ ์ „์ฒด ์ฝ”๋“œ
๋ฐ˜์‘ํ˜•

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

 

1926๋ฒˆ: ๊ทธ๋ฆผ

์–ด๋–ค ํฐ ๋„ํ™”์ง€์— ๊ทธ๋ฆผ์ด ๊ทธ๋ ค์ ธ ์žˆ์„ ๋•Œ, ๊ทธ ๊ทธ๋ฆผ์˜ ๊ฐœ์ˆ˜์™€, ๊ทธ ๊ทธ๋ฆผ ์ค‘ ๋„“์ด๊ฐ€ ๊ฐ€์žฅ ๋„“์€ ๊ฒƒ์˜ ๋„“์ด๋ฅผ ์ถœ๋ ฅํ•˜์—ฌ๋ผ. ๋‹จ, ๊ทธ๋ฆผ์ด๋ผ๋Š” ๊ฒƒ์€ 1๋กœ ์—ฐ๊ฒฐ๋œ ๊ฒƒ์„ ํ•œ ๊ทธ๋ฆผ์ด๋ผ๊ณ  ์ •์˜ํ•˜์ž. ๊ฐ€๋กœ๋‚˜ ์„ธ๋กœ

www.acmicpc.net


BFS์˜ ๊ฐœ๋…์„ ๊ฐ€์žฅ ์ž˜ ์ดํ•ดํ•  ์ˆ˜ ์žˆ๋Š” ๋ฌธ์ œ๋ผ๊ณ  ํ•  ์ˆ˜ ์žˆ๋‹ค. ์ฐจ๊ทผ์ฐจ๊ทผ ํ•œ๋ฒˆ ํ’€์–ด๋ณด๋„๋ก ํ•˜์ž.

โœ๏ธ ๋ฌธ์ œ

 

๐Ÿ” ๋ฌธ์ œ ํ•ด๊ฒฐ

๊ฐ’์ด 1์ด๋ฉด ์ƒ‰์น ์ด ๋œ ๋ถ€๋ถ„์ด๋‹ˆ๊นŒ, ๋ชจ๋“  ๊ทธ๋ฆผ์„ ์ „๋ถ€ ๋Œ๋ฉด์„œ 1์ด๊ฑฐ๋‚˜ ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ ๊ทธ๋ฆผ์„ ์ฒดํฌํ•˜๋ฉด์„œ ์ฒ˜๋ฆฌํ•ด์ฃผ๋ฉด ๋  ๊ฒƒ ๊ฐ™๋‹ค.

์šฐ์„  ๋ชจ๋“  ๊ทธ๋ฆผ์„ 2์ฐจ์› ๋ฐฐ์—ด์— ๋‹ด์•„์ฃผ๋„๋ก ํ•œ๋‹ค. (StringTokenizer๋ฅผ ์ด์šฉํ•ด์„œ ๊ฐ๊ฐ ์›์†Œ๋ฅผ ๋„ฃ์–ด์ค€๋‹ค.)

arr = new int[n][m];

// ๋ฐฐ์—ด๊ฐ’ ์„ธํŒ…
for(int i=0; i<n; i++){
    st = new StringTokenizer(bf.readLine());
    for(int j=0; j<m; j++){
        arr[i][j] = Integer.parseInt(st.nextToken());
    }
}

 

๊ทธ๋Ÿผ ์ด์ œ ๋ชจ๋“  ๋ฐฐ์—ด์˜ ์›์†Œ๋“ค์„ ์ˆœํšŒํ•˜๋ฉด์„œ, 0 ์ด๊ฑฐ๋‚˜ ๋ฐฉ๋ฌธํ•œ ๊ทธ๋ฆผ๋“ค์€ ๊ฑด๋„ˆ๋›ฐ์–ด์ฃผ๋„๋ก ํ•œ๋‹ค.

๊ทธ๋ฆฌ๊ณ , ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์•˜๊ฑฐ๋‚˜ 1(์ƒ‰์น )์ธ ๊ทธ๋ฆผ์€ ํ์— ๋„ฃ์–ด์„œ ์—ฐ๊ฒฐ๋œ ๊ทธ๋ฆผ์„ ์ฐพ๋„๋ก ํ• ๊ฑด๋ฐ, ์ด๋•Œ ์ค‘์š”ํ•œ ์ ์€ ํ(Queue)๋ฅผ ์ด์šฉํ•˜์—ฌ ์—ฐ๊ฒฐ๋œ ๊ทธ๋ฆผ์„ ์ฐพ๊ฒŒ ํ•  ๊ฒƒ์ด๋‹ค. ์–ด๋–ป๊ฒŒ ํ•˜๋А๋ƒ.. ํ์— ๋จผ์ € ๋„ฃ์—ˆ๋˜ ์›์†Œ๋Š” ํ•ด๋‹น ๊ทธ๋ฆผ์˜ ์ฒซ๋ฒˆ์งธ ์‹œ์ž‘์ ์ด ๋˜๋Š” ๊ฒƒ์ด๋‹ค. 

๊ทธ๋ ‡๋‹ค๋ฉด, ์ฒซ๋ฒˆ์งธ ์‹œ์ž‘์ ์„ ๊ฐ€์ง€๊ณ  ์œ„, ์•„๋ž˜, ์˜ค๋ฅธ์ชฝ, ์™ผ์ชฝ์„ ์ฐพ์•„์„œ 1์ธ ๊ทธ๋ฆผ์„ ๋˜ ํ์— ๋‹ด๊ณ , ๋‹ค์‹œ ํ์—์„œ ๊บผ๋‚ด์„œ ๋˜‘๊ฐ™์ด ๋ฐ˜๋ณตํ•˜๋ฉด ๋์ด๋‹ค.

 

๋จผ์ € ํ์— ์ขŒํ‘œ๋ฅผ ๋„ฃ์–ด์ฃผ๊ธฐ ์œ„ํ•ด์„œ Pair๋ผ๋Š” ํด๋ž˜์Šค๋ฅผ ์ƒ์„ฑํ•˜์—ฌ ๋„ฃ์–ด์ฃผ๋„๋ก ํ•œ๋‹ค. 

public class Pair {
	int x, y;
    
    public Pair(int x, int y){
    	this.x = x;
        this.y = y;
    }
    
    public void getX(){
    	return x;
    }
    
    public void getY(){
    	return y;
    }
    
    public int setX(int x){
    	this.x = x;
    }
    
    public int setY(int y){
    	this.y = y;
    }
}

 

์ด์ œ ํ๋ฅผ ์ด์šฉํ•ด์„œ BFS๋ฅผ ๊ตฌํ˜„ํ•ด๋ณผ ๊ฒƒ์ด๋‹ค. ๊ทธ๋ฆฌ ์–ด๋ ต์ง€ ์•Š์œผ๋‹ˆ ์•„๋ž˜ ์ฝ”๋“œ๋ฅผ ์ฐธ๊ณ ํ•˜๋ฉด์„œ ๊ตฌํ˜„ํ•ด๋ณด์ž.

// ์ˆœ์„œ๋Œ€๋กœ, ์˜ค๋ฅธ์ชฝ, ์•„๋ž˜, ์™ผ์ชฝ, ์œ„์ชฝ ์ขŒํ‘œ๋ฅผ ๊ณ„์‚ฐํ•  ์ˆ˜ ์žˆ๋‹ค.
int[] dx = {1, 0 , -1, 0);
int[] dy = {0, -1, 0, 1};

for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
    	if (arr[i][j] == 0 || visit[i][j]) {
        	continue;	// ์ƒ‰์น ์ด ์•ˆ๋๊ฑฐ๋‚˜, ๋ฐฉ๋ฌธํ–ˆ์„ ๋•Œ PASS!
        }
        
        visit[i][j] = true;	// ๋ฐฉ๋ฌธ ์ฒ˜๋ฆฌ!
        qu.offer(new Pair(i, j));	// ํ•ด๋‹น ์ขŒํ‘œ๋ฅผ ๋„ฃ์–ด์ค€๋‹ค.
        count++;
        area = 0;
        
        while(!qu.isEmpty()) {
            Pair p = qu.poll();
            area++;
            
            for(int k = 0; k < 4; k++) {
            	int n_X = p.x + dx[k];
                int n_Y = p.y + dy[k];
                
                // ์ƒˆ๋กœ ๊ณ„์‚ฐํ•œ ์ขŒํ‘œ๊ฐ€ 0๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜, ๋ฒฝ์— ๋ถ€๋”ชํžŒ๋‹ค๋ฉด PASS!
                if(n_X < 0 || n_X >= n || n_Y < 0 || n_Y >= m){
                	continue;
                }
                
                if(arr[n_X][x_Y] == 1 && visit[n_X][n_Y]){
                	qu.offer(new Pair(n_X, n_Y));
                    visit[n_X][n_Y] = true;
                }
            }
        }
        if (max > area) {
        	max = area;	// ์ตœ๋Œ€์ธ ๊ทธ๋ฆผ์„ ์ฐพ๋Š”๋‹ค.
        }
    }
}

์—ฌ๊ธฐ์„œ ๊ฐ€์žฅ ์ค‘์š”ํ•œ ์ ์€, ์ƒˆ๋กœ์šด ์ขŒํ‘œ๋ฅผ ๊ณ„์‚ฐํ•  ๋•Œ ๋ฒฝ์— ๋ถ€๋”ชํžˆ๊ฑฐ๋‚˜, ๊ทธ๋ฆผ์˜ ๊ธธ์ด์— ๋ฒ—์–ด๋‚˜๋ฉด PASSํ•ด์ค˜์•ผ ํ•œ๋‹ค!

๊ทธ๋ฆฌ๊ตฌ ๋งˆ์ง€๋ง‰์—๋Š” ๊ทธ๋ฆผ์˜ ๋„“์ด๊ฐ€ ์ตœ๋Œ€์ธ ๊ฒƒ์„ ์ฐพ์•„์„œ max ๋ณ€์ˆ˜์— ๋‹ด์•„์ฃผ๋ฉด ๋œ๋‹ค!

 

๐Ÿ“ ์ „์ฒด ์ฝ”๋“œ

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

public class Main {
    static int n, m;
    static int[][] arr;
    static boolean[][] visit;
    static int[] dx;
    static int[] dy;
    static Queue<Pair> qu;

    public static void main(String args[]) throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        
        arr = new int[n][m];
        visit = new boolean[n][m];
        qu = new LinkedList<>();
        
        dx = new int[]{1, 0, -1, 0};
        dy = new int[]{0, 1, 0, -1};
        
        // ๋ฐฐ์—ด๊ฐ’ ์„ธํŒ…
        for(int i=0; i<n; i++){
            st = new StringTokenizer(bf.readLine());
            for(int j=0; j<m; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        // ์‹œ์ž‘!
        int count = 0;
        int area = 0;
        int max = 0;
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                // 0์ด๊ฑฐ๋‚˜ ๋ฐฉ๋ฌธํ•œ์ ์ด ์žˆ์œผ๋ฉด ์ƒ๋žต.
                if(arr[i][j] == 0 || visit[i][j]){
                    continue;
                }
                count++;    // 1์ด๊ณ , ๋ฐฉ๋ฌธ์„ ํ•˜์ง€ ์•Š์•˜์œผ๋ฏ€๋กœ ์‹œ์ž‘์ ์ด ๋˜๋‹ˆ๊นŒ +1
                qu.offer(new Pair(i, j));   // ํ์— ์ขŒํ‘œ๋ฅผ ๋„ฃ์–ด์ค€๋‹ค.
                visit[i][j] = true;     // ๋ฐฉ๋ฌธ์ฒ˜๋ฆฌ!
                area = 0;    // 0์ด๋ฉด ๊ทธ๋ฆผ์ด ๋Š๊ฒผ์œผ๋ฏ€๋กœ area = 0!
                while(!qu.isEmpty()){
                    Pair p = qu.poll();
                    area++; // ๋„“์ด +1
                    for(int k = 0; k < 4; k++){
                        int n_x = p.x + dx[k];
                        int n_y = p.y + dy[k];
                        if(n_x < 0 || n_x >= n || n_y < 0 || n_y >= m){
                            continue;
                        }
                        if(arr[n_x][n_y] == 1 && !visit[n_x][n_y]){
                            qu.offer(new Pair(n_x, n_y));
                            visit[n_x][n_y] = true;
                        }
                    }
                }
                if(area > max){
                    max = area;
                }
            }
            
        }
        System.out.println(count);
        System.out.println(max);
    }
    
    public static class Pair{
        int x;
        int y;
        
        public Pair(int x, int y){
            this.x = x;
            this.y = y;
        }
        
        public int getX(){
            return x;
        }
        public int getY(){
            return y;
        }
        public void setX(int x){
            this.x = x;
        }
        public void setY(int y){
            this.y = y;
        }
        
    }
}
๋ฐ˜์‘ํ˜•
์ €์ž‘์žํ‘œ์‹œ (์ƒˆ์ฐฝ์—ด๋ฆผ)
  1. โœ๏ธ ๋ฌธ์ œ
  2. ๐Ÿ” ๋ฌธ์ œ ํ•ด๊ฒฐ
  3. ๐Ÿ“ ์ „์ฒด ์ฝ”๋“œ
'๐Ÿ“œ ์ฝ”๋”ฉํ…Œ์ŠคํŠธ/BAEKJOON\BFS, DFS' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
  • ๋ฐฑ์ค€ 2206๋ฒˆ : ๋ฒฝ ๋ถ€์ˆ˜๊ณ  ์ด๋™ํ•˜๊ธฐ (JAVA) ๋ฌธ์ œ ํ’€์ด
  • ๋ฐฑ์ค€ 7569๋ฒˆ : ํ† ๋งˆํ†  (JAVA) ๋ฌธ์ œ ํ’€์ด
  • ๋ฐฑ์ค€ 7576๋ฒˆ : ํ† ๋งˆํ†  (JAVA) ๋ฌธ์ œ ํ’€์ด
  • ๋ฐฑ์ค€ 2178๋ฒˆ : ๋ฏธ๋กœ ํƒ์ƒ‰ (JAVA) ๋ฌธ์ œ ํ’€์ด
iseunghan
iseunghan
๊พธ์ค€ํ•˜๊ฒŒ ์—ด์‹ฌํžˆ..
iseunghan๊พธ์ค€ํ•˜๊ฒŒ ์—ด์‹ฌํžˆ..
iseunghan
iseunghan

๊ณต์ง€์‚ฌํ•ญ

  • ์–ด์ œ๋ณด๋‹ค ๋‚˜์€ ์˜ค๋Š˜์ด ๋˜๊ธฐ ์œ„ํ•ด ๐Ÿ”ฅ
  • ๋ถ„๋ฅ˜ ์ „์ฒด๋ณด๊ธฐ (261)
    • ๐Ÿ’ Spring (14)
      • ๊ฐœ๋… ๋ฐ ์ดํ•ด (2)
      • Spring ํ•ต์‹ฌ ๊ธฐ์ˆ  (24)
      • Spring REST API (8)
      • Spring MVC, DB ์ ‘๊ทผ ๊ธฐ์ˆ  (7)
      • Spring Security (23)
      • Spring in Action (1)
    • ๐ŸŒป JAVA (84)
      • ์ž๋ฐ” ORM ํ‘œ์ค€ JPA ํ”„๋กœ๊ทธ๋ž˜๋ฐ (20)
      • ์•Œ๊ณ ๋ฆฌ์ฆ˜, ์ž๋ฃŒ๊ตฌ์กฐ (13)
      • ๋””์ž์ธ ํŒจํ„ด (7)
      • ์ •๋ฆฌ์ •๋ฆฌ์ •๋ฆฌ (43)
      • JUnit (1)
    • ๐Ÿ”– Snippets (3)
      • Javascript (3)
    • โš™๏ธ Devops (22)
      • โ› Git (11)
      • ๐Ÿณ Docker (6)
      • ๐Ÿง Linux (3)
      • ๐ŸŒˆ Jenkins (1)
      • ๐Ÿ“ฌ Kafka (1)
    • ๐Ÿ’ฌ ETC.. (4)
      • ๐Ÿ’ป macOS (2)
    • ๐ŸŒง๏ธ ORM (2)
      • JPA (2)
    • ๐Ÿ Python (2)
    • ๐Ÿ“š Databases (15)
      • ์˜ค๋ผํด๋กœ ๋ฐฐ์šฐ๋Š” ๋ฐ์ดํ„ฐ๋ฒ ์ด์Šค ๊ฐœ๋ก ๊ณผ ์‹ค์Šต(2ํŒ) (3)
      • RealMySQL 8.0 (8)
    • ๐Ÿ”ฅ Computer Science (5)
      • ๐Ÿ“ก ๋„คํŠธ์›Œํฌ (5)
    • ๐Ÿท๏ธ ํ˜‘์—… (1)
    • ๐Ÿ“œ ์ฝ”๋”ฉํ…Œ์ŠคํŠธ (38)
      • BAEKJOON\์ˆ˜ํ•™ 1, ์ˆ˜ํ•™ 2 (8)
      • BAEKJOON\์žฌ๊ท€ (5)
      • BAEKJOON\๋ธŒ๋ฃจํŠธ ํฌ์Šค (3)
      • BAEKJOON\์ •๋ ฌ (1)
      • BAEKJOON\๋ฐฑํŠธ๋ž˜ํ‚น (5)
      • BAEKJOON\BFS, DFS (6)
      • BAEKJOON\์ด๋ถ„ํƒ์ƒ‰ (1)
      • BAEKJOON\๋‹ค์ด๋‚˜๋ฏน ํ”„๋กœ๊ทธ๋ž˜๋ฐ (9)
      • BAEKJOON\๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜ (0)
    • โœจ ISEUNGHAN (1)

์ธ๊ธฐ ๊ธ€

์ตœ๊ทผ ๊ธ€

์ „์ฒด
์˜ค๋Š˜
์–ด์ œ
๋ฐ˜์‘ํ˜•
hELLO ยท Designed By ์ •์ƒ์šฐ.
iseunghan
๋ฐฑ์ค€ 1926๋ฒˆ : ๊ทธ๋ฆผ (JAVA) ๋ฌธ์ œ ํ’€์ด
์ƒ๋‹จ์œผ๋กœ

ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”

๊ฐœ์ธ์ •๋ณด

  • ํ‹ฐ์Šคํ† ๋ฆฌ ํ™ˆ
  • ํฌ๋Ÿผ
  • ๋กœ๊ทธ์ธ

๋‹จ์ถ•ํ‚ค

๋‚ด ๋ธ”๋กœ๊ทธ

๋‚ด ๋ธ”๋กœ๊ทธ - ๊ด€๋ฆฌ์ž ํ™ˆ ์ „ํ™˜
Q
Q
์ƒˆ ๊ธ€ ์“ฐ๊ธฐ
W
W

๋ธ”๋กœ๊ทธ ๊ฒŒ์‹œ๊ธ€

๊ธ€ ์ˆ˜์ • (๊ถŒํ•œ ์žˆ๋Š” ๊ฒฝ์šฐ)
E
E
๋Œ“๊ธ€ ์˜์—ญ์œผ๋กœ ์ด๋™
C
C

๋ชจ๋“  ์˜์—ญ

์ด ํŽ˜์ด์ง€์˜ URL ๋ณต์‚ฌ
S
S
๋งจ ์œ„๋กœ ์ด๋™
T
T
ํ‹ฐ์Šคํ† ๋ฆฌ ํ™ˆ ์ด๋™
H
H
๋‹จ์ถ•ํ‚ค ์•ˆ๋‚ด
Shift + /
โ‡ง + /

* ๋‹จ์ถ•ํ‚ค๋Š” ํ•œ๊ธ€/์˜๋ฌธ ๋Œ€์†Œ๋ฌธ์ž๋กœ ์ด์šฉ ๊ฐ€๋Šฅํ•˜๋ฉฐ, ํ‹ฐ์Šคํ† ๋ฆฌ ๊ธฐ๋ณธ ๋„๋ฉ”์ธ์—์„œ๋งŒ ๋™์ž‘ํ•ฉ๋‹ˆ๋‹ค.