글 읽기 - 어느 부분에서 틀리는지 잘 모르겠습니다. ㅠ

wow1514 8년 전 0

비트연산을 이용해

벽이 아닌곳을 찾아서 bfs로 탐색하게 했습니다.

bfs로 탐색하면서 방의 넓이를 조사했습니다.

또한 벽을 허물때는

첫 시작지에서 부터 동,서,남,북 방향으로 벽을 부수어 현재 방번호와 다를 경우

두 방의 넓이를 구하여, 벽을 허물었을때 가장 큰 방의 크기를 구했습니다.

잘못된 부분을 아신다면 답변 부탁드리겠습니다...

import java.util.Scanner;

public class wall{
	static int M,N;
	static int[][] wall;
	static int[][] visited;
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		M = sc.nextInt();
		N = sc.nextInt();
		wall = new int[N+1][M+1];
		for(int i = 1; i <= N; i++){
			for(int j = 1; j <= M; j++){
				wall[i][j] = sc.nextInt();
			}
		}
		visited = new int[N+1][M+1];
		int[] space = new int[2000000];
		int max = 0;
		int room = 0;
		int tmp = 0;
		int total = 0;
		for(int i = 1; i <= N; i++){
			for(int j = 1; j <= M; j++){
				tmp = 0;
				if(visited[i][j] == 0){
					room += 1;
					tmp = BFS(visited,i,j,room);
					if(tmp > max)
						max = tmp;
					space[room] = tmp;
					if(room == 1)
						total = space[room];
					else if(room != 1){
						int sum = 0;
						if(j-1 > 0 && visited[i][j-1] != 0 && visited[i][j-1] != visited[i][j]){
							sum = space[room] + space[visited[i][j-1]];
							if(sum > total)
								total = sum;
						}
						if(j+1 <= M && visited[i][j+1] != 0 && visited[i][j+1] != visited[i][j]){
							sum = space[room] + space[visited[i][j+1]];
							if(sum > total)
								total = sum;
						}
						if(i-1 > 0 && visited[i-1][j] != 0 && visited[i-1][j] != visited[i][j]){
							sum = space[room] + space[visited[i-1][j]];
							if(sum > total)
								total = sum;
						}
						if(i+1 <= N && visited[i+1][j] != 0 && visited[i+1][j] != visited[i][j]){
							sum = space[room] + space[visited[i+1][j]];
							if(sum > total)
								total = sum;
						}
					}
				}
			}
		}

		System.out.println(room);
		System.out.println(max);
		System.out.println(total);

		sc.close();
	}

	static int BFS(int[][] visited,int startX,int startY,int number){
		Queue q = new Queue(2000001);
		visited[startX][startY] = number;
		q.push(startX);
		q.push(startY);
		int cnt = 1;
		
		while(!q.isEmpty()){
			int newX = q.pop();
			int newY = q.pop();
			
			int direction = (byte)wall[newX][newY] ^ (byte)15;
			//System.out.println(direction);
			//서
			if(((byte)direction & (byte)1) == 1 && newY - 1 > 0 && visited[newX][newY-1] == 0){
				visited[newX][newY-1] = number;
				cnt += 1;
				q.push(newX);
				q.push(newY-1);
			}
			//북
			if(((byte)direction & (byte)2) == 2 && newX - 1 > 0 && visited[newX-1][newY] == 0){
				visited[newX-1][newY] = number;
				cnt += 1;
				q.push(newX-1);
				q.push(newY);
			}
			//동
			if(((byte)direction & (byte)4) == 4 && newY + 1 <= M && visited[newX][newY+1] == 0){
				visited[newX][newY+1] = number;
				cnt += 1;
				q.push(newX);
				q.push(newY+1);
			}
			//남
			if(((byte)direction & (byte)8) == 8 && newX + 1 <= N && visited[newX+1][newY] == 0){
				visited[newX+1][newY] = number;
				cnt += 1;
				q.push(newX+1);
				q.push(newY);
			}
		}
		
		return cnt;
	}
}
class Queue{
	private int front;
	private int rear;
	private int[] arr;
	
	public Queue(int size){
		front = -1;
		rear = -1;
		arr = new int[size];
	}
	public void push(int item){
		arr[++rear] = item;
	}
	public int pop(){
		return arr[++front];
	}
	public boolean isEmpty(){
		return(front==rear);
	}
}

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

문제

문제

출처

ICPC

어느 부분에서 틀리는지 잘 모르겠습니다. ㅠ

wow1514 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말