[Baekjoon] 27211_도넛 행성

Gold V

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

---

< 도넛 행성>

 

문제 풀이

 

비어있는 곳에서 상하좌우를 탐색하여 비어있는 곳을 찾아 이동한다.

범위 밖으로 이동할 때는 이어진 곳을 잘 생각하여 이동한다.

 

 

 - 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 _27211_ { // 도넛 행성
	static int arr[][], result, n, m;
	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=new StringTokenizer(bf.readLine());

		n=Integer.parseInt(st.nextToken());
		m=Integer.parseInt(st.nextToken());

		arr=new int[n][m];
		visited=new boolean[n][m];
		result=0;

		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());
				if(arr[i][j]==1) visited[i][j]=true;
			}
		}
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				if(!visited[i][j]) {
					visited[i][j]=true;
					result+=1;
					search(i,j);
				}
			}
		}
		System.out.println(result);
	}

	private static void search(int i, int j) {
		Queue<int[]> queue=new LinkedList<>();
		queue.add(new int[] {i,j});

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

 

Main

-  n, m 입력

- arr : 도넛 정보

- visited : 방문 여부

- result: 탐험할 수 있는 구역의 개수

- 도넛 행성 정보를 입력받은 후 숲으로 막혀 있는 곳이라면 방문 여부를 true로 저장

- 전체 도넛 행성을 탐험하며 아직 방문하지 않은 곳이라면 탐험을 시작

 

Search

- queue가 빌 때까지 반복하면서 값을 하나 뽑아 상하좌우 탐색

- 상하좌우를 탐색하며 범위 밖이면 도넛 행성이 이어져 있으므로 좌표를 수정하여 방문 표시 및 queue에 추가

 

---

생각🤔

 

---