[백준] 1012번:유기농 배추(Java 자바)

[백준] 1012번:유기농 배추(Java 자바)

728x90

문제

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

풀이 및 소스코드

배추가 있는 곳이면 지렁이 한 마리만 카운트 해주고 연결되어있는 곳들은 bfs를 돌려 일반땅으로 만든다. (1->0)

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; StringBuilder sb = new StringBuilder(); int t = Integer.parseInt(br.readLine()); for(int tt=0;tt b_q = new LinkedList(); for(int i=0;i q = new LinkedList(); if(map[tmp.x][tmp.y]==0) continue; // 연결되어있어서 이미 0으로 바뀐 곳이라면 더 이상 알아보지 않아도 되므로 컨티뉴 q.add(new node(tmp.x, tmp.y)); // 위에서 컨티뉴 되지 않았음 -> 아직 1인 곳이므로 bfs를 돌려 인접한 곳 모두 일반 땅으로 바꿔준다. // 즉 방문처리 해주기 위한 큐 res++; // 지렁이 카운트 map[tmp.x][tmp.y] = 0; // 이곳이 방문처리 하는 곳. while(!q.isEmpty()) { // tmp와 연결되어있는 곳들은 벌레 한마리면 충분하니까 bfs로 0으로 바꿔준다. node now = q.poll(); for(int i=0;i<4;i++) { int nowx = now.x+dx[i]; int nowy = now.y+dy[i]; if(0>nowx||0>nowy||n<=nowx||m<=nowy) { continue; } if(map[nowx][nowy] == 1) { map[nowx][nowy] = 0; q.add(new node(nowx, nowy)); } } } } sb.append(res).append("

"); } System.out.println(sb); } } class node{ int x,y; public node(int x, int y) { super(); this.x = x; this.y = y; } }

반응형

from http://jainn.tistory.com/340 by ccl(A) rewrite - 2021-12-06 00:01:23