[파이썬, 자바] 백준 1012 : 유기농 배추 (실버2)

[파이썬, 자바] 백준 1012 : 유기농 배추 (실버2)

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

---

풀이

방향성 생각

• 배추 찾으면 BFS 돌리기
• BFS 돌린 횟수 카운팅해서 출력하기.

 

---

파이썬

from collections import deque
import sys

input = lambda : sys.stdin.readline().rstrip()
inside = lambda x,y : 0<=x<W and 0<=y<H
dire = [(1,0),(0,1),(-1,0),(0,-1)]

def bfs(sx,sy):

    Q = deque([(sx,sy)])
    while Q:
        x,y = Q.popleft()

        for dx,dy in dire:
            nx,ny = x+dx, y+dy

            if inside(nx,ny) and not V[ny][nx] and arr[ny][nx]:
                V[ny][nx] = True
                Q.append((nx,ny))

for _ in range(int(input())):
    W,H,K = map(int,input().split())

    arr = [[0]*W for _ in range(H)]
    for _ in range(K):
        x,y = map(int,input().split())
        arr[y][x] = 1

    V = [[False]*W for _ in range(H)]
    answer = 0
    for i in range(H):
        for j in range(W):
            if arr[i][j] and not V[i][j]:
                bfs(j,i)
                answer += 1

    print(answer)

• 테케 받아서 BFS 돌리기

자바

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

public class Main {

    public static int T, H, W, K;
    public static int[][] dire = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            String[] line = br.readLine().split(" ");
            W = Integer.parseInt(line[0]);
            H = Integer.parseInt(line[1]);
            K = Integer.parseInt(line[2]);

            int[][] arr = new int[H][W];

            for (int k = 0; k < K; k++) {
                String[] loc = br.readLine().split(" ");
                int x = Integer.parseInt(loc[0]);
                int y = Integer.parseInt(loc[1]);
                arr[y][x] = 1;
            }

            boolean[][] V = new boolean[H][W];
            int answer = 0;

            for (int i = 0; i < H; i++) {
                for (int j = 0; j < W; j++) {
                    if (arr[i][j] == 1 && !V[i][j]) { 
                        bfs(j, i, V, arr);
                        answer++;
                    }
                }
            }

            System.out.println(answer);
        }
    }

    public static void bfs(int sx, int sy, boolean[][] V, int[][] arr) {
        Deque<int[]> Q = new ArrayDeque<>();
        Q.offer(new int[] {sx, sy});
        V[sy][sx] = true;

        while (!Q.isEmpty()) {
            int[] loc = Q.poll();
            int x = loc[0], y = loc[1];

            for (int[] dir : dire) {
                int nx = x + dir[0];
                int ny = y + dir[1];

                if (nx >= 0 && nx < W && ny >= 0 && ny < H && arr[ny][nx] == 1 && !V[ny][nx]) {
                    V[ny][nx] = true;
                    Q.offer(new int[] {nx, ny});
                }
            }
        }
    }
}

• 입력은 BufferedReader br = new BufferedReader (new InputStreamReader (System.in))
• 줄마다 읽어서 string에 할당하고 split으로 쪼개거나, parseInt로 차례로 빼기.
• Deque에선 offer/poll + First()/Last()가 기본
• 단순 방문처리만 할거라 int 대신 boolean으로 받았다. int도 상관없긴 한데..
• dire같은거는 for each로 dir : dire로 받았다.
• 변수명을 덮어쓰는게 불편해서 한 번에 변수명을 잘 할당하고 시작하자.

---

코멘트

• 자바 너무길다