[백준 2234번] 성곽 (java)

2234번: 성곽

 

• room 이차원 배열을 만들어서 방번호를 넣어준다. room 이차원 배열이 여기서 방문처리 역할을 한다. room[m][n] != 0 이미 방번호가 배정된 것이므로(방번호는 1번부터 시작하는 걸로 설정) 방문한 것이나 마찬가지가 된다.

• area 일차원 배열에는 해당 방들의 넓이를 넣어준다. ex) area[1] : 1번 방의 넓이, area[2] : 2번 방의 넓이 문제에서 성곽의 최대 넓이는 n=50, m=50 일 때 2500이고, 모든 공간마다 벽으로 막혀있다고 할 때, 최대 2500개의 방이 만들어질 수 있으므로 area 배열의 크기는 2501로 설정하였다. int[] area= new int[2501];

 

[이 성의 방의 개수, 가장 넓은 방의 넓이]

room[m][n] = 0(미방문)인 경우에만 해당 위치를 시작점으로 하여 bfs 탐색을 진행하면서 현재 공간을 기준으로 그 공간의 '벽에 대한 정보(0~15)'를 계속 2로 나누어서 나머지가 0인 경우(둘 사이에 벽이 없는 경우)에만 같은 방에 속하는 공간들에 같은 방번호를 부여한다.

 

그리고 bfs 탐색을 하는 동안 큐에서 꺼내질 때마다 area[방번호]를 증가시킨다.

탐색을 마쳤을 때 최종 area[방번호]가 그 방의 넓이가 된다.

 

[하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기]

방들을 (0,0)위치부터 하나씩 탐색하면서, 벽이 있는 경우 벽을 사이에 둔 두 방의 넓이의 합을 구한다.

인접한 두 공간의 방번호가 각각 1과 2일 때, 두 방을 합친 넓이는 area[1] + area[2] 가 된다.

벽이 있는지 여부는 인접한 두 공간의 방번호가 다르면 둘 사이에 벽이 있다는 뜻이다.

특정 벽을 허물었을 때 두 방의 넓이의 합이 기존의 경우보다 더 클 경우, 계속 갱신시켜 나가면서 최대값을 구한다.

 

 

소스코드 :