BOJ::1012 유기농배추
https://www.acmicpc.net/problem/1012
BLOB의 갯수를 구하는 문제(사실 BLOB이라는 표현이 맞는표현인지는 잘 모르겠다..ㅎㅎㅎ)
BFS, DFS 이용하는 기본적인 문제
단순히 탐색하며 카운트만 증가시키면 되기 때문에 dfs로 코딩하는게 더 쉽고 빠른거 같다.
(실제 채점현황에서 속도 차이는 없음)
DFS를 이용한 풀이
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 | import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; class Main{ static int t,n,m,k,ax,ay; static int map[][]=new int[51][51]; static int dx[]={1,-1,0,0}; static int dy[]={0,0,1,-1}; public static void main(String args[]) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); t = Integer.parseInt(br.readLine()); for(int z = 0 ; z < t ; z++){ StringTokenizer st = new StringTokenizer(br.readLine()); n=Integer.parseInt(st.nextToken()); m=Integer.parseInt(st.nextToken()); k=Integer.parseInt(st.nextToken()); for(int i = 0 ; i < k ; i++){ st = new StringTokenizer(br.readLine()); int x = Integer.parseInt(st.nextToken()); int y = Integer.parseInt(st.nextToken()); map[x][y]=1; } int cnt=0; for(int i = 0 ; i < n ; i++){ for(int j = 0 ; j < m ; j++){ if(map[i][j]==1){ cnt++; dfs(i,j); } } } System.out.println(cnt); } } //깊이우선탐색 public static void dfs(int a,int b){ map[a][b]=0; for(int i = 0 ; i < 4 ; i++){ ax = a+dx[i]; ay = b+dy[i]; if((ax>=0&&ay>=0&&ax<n&&ay<m) && map[ax][ay]==1){ dfs(ax,ay); } } } } | cs |
BFS를 이용한 풀이
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 | import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; class Main{ static int t,n,m,k,ax,ay,x,y; static int map[][]=new int[51][51]; static int dx[]={1,-1,0,0}; static int dy[]={0,0,1,-1}; public static void main(String args[]) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); t = Integer.parseInt(br.readLine()); for(int z = 0 ; z < t ; z++){ StringTokenizer st = new StringTokenizer(br.readLine()); n=Integer.parseInt(st.nextToken()); m=Integer.parseInt(st.nextToken()); k=Integer.parseInt(st.nextToken()); for(int i = 0 ; i < k ; i++){ st = new StringTokenizer(br.readLine()); int x = Integer.parseInt(st.nextToken()); int y = Integer.parseInt(st.nextToken()); map[x][y]=1; } int cnt=0; for(int i = 0 ; i < n ; i++){ for(int j = 0 ; j < m ; j++){ if(map[i][j]==1){ cnt++; bfs(i,j); } } } System.out.println(cnt); } } public static void bfs(int a,int b){ map[a][b]=0; Queue<Node> q = new LinkedList(); q.add(new Node(a,b)); while(!q.isEmpty()){ x = q.peek().x; y = q.poll().y; for(int i = 0 ; i < 4 ; i++){ ax = x+dx[i]; ay = y+dy[i]; if((ax>=0&&ay>=0&&ax<n&&ay<m)&&map[ax][ay]==1){ map[ax][ay]=0; q.add(new Node(ax,ay)); } } } } } class Node{ int x; int y; Node(int _x, int _y){ x=_x; y=_y; } } | cs |