글 읽기 - 예제는 통과하는데 맵을 찍어봐도 어디서 잘못됐는지 모르겠습니다.

hik3562 4년 전 0

쓸대없는변수가 없지만

다음의방식으로 동작합니다.

Bfs로 안전영역을 1로채웁니다.

그리고 나머지 0인부분을 bfs로 찾습니다.

이를 어레이리스트에 넣고 소트한뒤

사이즈와 각인자를 순서대로 출력했습니다.

'''
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class BBC{
	int x;
	int y;
	BBC(int x, int y){
		this.x = x;
		this.y = y;
	}
}
public class Main {

	static int dx[] = {-1,1,0,0};
	static int dy[] = {0,0,-1,1};
	static int[][] visit;
	static int[][] visit2;
	static int[][] map;
	static int ans = 0;
	static int a;
	static int b;
	private static void BFS(int x, int y, int cnt) {

		Queue<BBC> q2 = new LinkedList<>();
		
		q2.add(new BBC(x,y));
		visit2[x][y] = cnt;
		while(!q2.isEmpty()) {
			BBC bbbbb = q2.remove();

			int tempx = bbbbb.x;
			int tempy = bbbbb.y;
			//System.out.println("tempx : "+tempx + "tempy : "+tempy);
			for(int i=0; i<4; i++) {
				int ddx = tempx + dx[i];
				int ddy = tempy + dy[i];
				
				if(ddx<0 || ddx>=b || ddy<0 || ddy>=a) continue;
				
				if(map[ddx][ddy]==0 && visit2[ddx][ddy] ==0 ) {
					ans+=1;
					q2.add(new BBC(ddx,ddy));
					visit2[ddx][ddy] = cnt;
				}
			}
		}
		
		
	}
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		//System.setIn(new FileInputStream("res/backjun_2583.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Queue<BBC> q = new LinkedList<>();
		StringTokenizer st = new StringTokenizer(br.readLine());
		ArrayList<Integer> al = new ArrayList<>();
		a = Integer.parseInt(st.nextToken());
		b = Integer.parseInt(st.nextToken());
		int c = Integer.parseInt(st.nextToken());
		
		
		map = new int[b][a];
		visit2 = new int[b][a];
		for(int i=0; i<c; i++) {
			visit = new int[b][a];
			st = new StringTokenizer(br.readLine());
			int z = Integer.parseInt(st.nextToken()); //0
			int x = Integer.parseInt(st.nextToken()); //2
			int m = Integer.parseInt(st.nextToken()); //4
			int v = Integer.parseInt(st.nextToken()); //4
			//System.out.println(z+" "+x+" "+m+" "+v);
			
			
			q.add(new BBC(z,x));
			while(!q.isEmpty()) {
				BBC bbc = q.remove();
				int tempx = bbc.x;
				int tempy = bbc.y;
				
				for(int l=0; l<4; l++) {
					
					int ddx = tempx + dx[l];
					int ddy = tempy + dy[l];
					if(ddx<0 || ddx>=b || ddy<0 || ddy>=a || 
							ddx<z || ddy<x || ddx>m-1 || ddy>v-1) continue;
					
					if(visit[ddx][ddy]==0) {
						visit[ddx][ddy] = 1;
						visit2[ddx][ddy] = 1;
						map[ddx][ddy] = 1;
						//System.out.println("ddx : "+ddx + " ddy : "+ddy);
						
						q.add(new BBC(ddx, ddy));
					}
				}
			}
		}
			/*
			for(int dd=0; dd<b; dd++) {
				for(int gg=0; gg<a; gg++) {
					System.out.print(visit2[dd][gg] +" ");
				}
				System.out.println();
			}*/
			int cnt = 1;
			for(int s=0; s<b; s++) {
				for(int h=0; h<a; h++) {
					if(map[s][h] == 0 && visit2[s][h] == 0) {
						ans+=1;
						BFS(s,h, ++cnt);
						//System.out.println(ans);
						al.add(ans);
						ans=0;
						
						
					}
					
					
				}
			}
			Collections.sort(al);
			System.out.println(al.size());
			for(int d = 0; d<al.size(); d++) {
				System.out.print(al.get(d)+" ");
			}
		}
		
		
	}
'''

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

예제는 통과하는데 맵을 찍어봐도 어디서 잘못됐는지 모르겠습니다.

hik3562 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말