[Baekjoon] 11123_양 한마리... 양 두마리...

Silver II

문제(출처: https://www.acmicpc.net/problem/11123)

---

< 양 한마리... 양 두마리... >

 

문제 풀이

 

bfs 탐색하여 양 무리를 찾아 해결할 수 있었다.

 

 

 - my solution (Java)

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 _11123_ { // 양 한마리... 양 두마리...
	static int arr[][], H, W;
	static boolean visited[][];
	static int[] dx= {-1,1,0,0};
	static int[] dy= {0,0,-1,1};
	public static void main(String[] args) throws IOException {
		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int T=Integer.parseInt(bf.readLine());
		for(int i=0; i<T; i++) {
			st=new StringTokenizer(bf.readLine());
			H=Integer.parseInt(st.nextToken()); // 높이
			W=Integer.parseInt(st.nextToken()); // 너비
			arr=new int[H][W];
			visited=new boolean[H][W];
			for(int j=0; j<H; j++) { // input
				String str=bf.readLine();
				for(int k=0; k<W; k++) {
					arr[j][k]=str.charAt(k);
					if(arr[j][k]=='.') visited[j][k]=true;
				}
			}
			int result=0;
			for(int j=0; j<H; j++) {
				for(int k=0; k<W; k++) {
					if(!visited[j][k]) {
						result+=1;
						search(j,k);
					}
				}
			}
			System.out.println(result);
		}
	}
	private static void search(int j, int k) {
		Queue<int[]>queue=new LinkedList<>();
		queue.add(new int[] {j,k});
		visited[j][k]=true;

		while(!queue.isEmpty()){
			int temp[]=queue.poll();
			for(int i=0; i<4; i++) {
				int x=temp[0]+dx[i];
				int y=temp[1]+dy[i];
				if(x>=0 && x<H && y>=0 && y<W && !visited[x][y]) {
					visited[x][y]=true;
					queue.add(new int[] {x,y});
				}
			}
		}
	}
}

 

Main

- 테스트 케이스의 수 (T) 입력

- 그리드의 높이 (H), 너비 (W) 입력

- 그리드 입력과 동시에 풀은 필요 없으므로 방문 표시

- 아직 방문하지 않은 곳은 양들이 있는 곳이므로 함수 호출

- 양의 무리 (result) 출력

 

search

- queue가 빌 때까지 반복하여 queue 값을 뽑아 상하좌우 이동하여 그리드 범위 안이며 아직 방문하지 않은 곳이면 방문 표시 및 queue에 추가

---

생각🤔

 

---