[백준 2234] 성곽 (자바)

백준 2234번 성곽 (자바)

 

 

 

출처

www.acmicpc.net/problem/2234

2234번: 성곽

 

 

 

문제

대략 위의 그림과 같이 생긴 성곽이 있다. 굵은 선은 벽을 나타내고, 점선은 벽이 없어서 지나다닐 수 있는 통로를 나타낸다. 이러한 형태의 성의 지도를 입력받아서 다음을 계산하는 프로그램을 작성하시오.

1. 이 성에 있는 방의 개수
2. 가장 넓은 방의 넓이
3. 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기

위의 예에서는 방은 5개고, 가장 큰 방은 9개의 칸으로 이루어져 있으며, 위의 그림에서 화살표가 가리키는 벽을 제거하면 16인 크기의 방을 얻을 수 있다.

성은 m×n(1 ≤ m, n ≤ 50)개의 정사각형 칸으로 이루어진다. 성에는 최소 두 개의 방이 있어서, 항상 하나의 벽을 제거하여 두 방을 합치는 경우가 있다.

 

 

 

입력

첫째 줄에 두 정수 n, m이 주어진다. 다음 m개의 줄에는 n개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, 동쪽에 벽이 있을 때는 4를, 남쪽에 벽이 있을 때는 8을 더한 값이 주어진다. 참고로 이진수의 각 비트를 생각하면 쉽다. 따라서 이 값은 0부터 15까지의 범위 안에 있다.

 

 

 

출력

첫째 줄에 1의 답을, 둘째 줄에 2의 답을, 셋째 줄에 3의 답을 출력한다.

 

 

 

 

입출력 예

입출력 예1

 

 

 

걸린시간

오늘부터 문제 푸는데 걸린 시간을 추가하려 한다.

 

 

 

접근 방법

BFS/DFS를 사용해야 하는 문제로 총 3개의 값을 구해야 한다.

방의 개수, 가장 넓은 방의 넓이, 벽 제거 시 얻을 수 있는 제일 큰 방의 크기

 

첫 번째, 방의 개수는 bfs를 통해 탐색한 방개수만큼 출력한다.

 

두 번째, 가장 넓은 방의 넓이는 방의 개수를 탐색할 때 각각 방의 넓이를 구해 최대 넓이를 구한다.

 

세 번째, 벽 제거 시 얻을 수 있는 제일 큰 방의 크기는 위 두 연산 시 각 방에다가 <방 번호, 방 넓이>를 넣어준다. 이후, 인접 방의 벽을 제거 후 두 방 넓이의 합을 구한다.

 

1. 주어지는 값을 이진수로 변경하여 벽이 있는 방향을 파악해야 하므로 StringFormat을 사용해 이진수를 저장한다.

    이후 4자리의 이진수에서 0번째는(1000) 남, 1번째는(0100) 동, 2번째는(0010) 북, 3번째는(0001) 서로 구분하여 벽의      위치를 파악하여 탐색 여부를 판별한다.

 

2. bfs를 실행해 전체 방의 개수를 구한다.

    (탐색 시에 첫 번째와 두 번째 답을 모두 구할 것이다.)

    탐색 시작 시마다 roomCnt를 +1 하여 방의 개수를 구한다.(roomCnt)

    그리고, 탐색할 때마다 방 넓이를 +1 하여 넓이를 구한다.(roomWidth)

    매개변수로 보낸 방 번호를 map배열에 넣어 각각의 방이 자신의 방 번호를 가지게 한다.

 

3. bfs연산 때마다 HashMap에 방 번호를 키값으로 가지고 방 넓이를 value에 넣는다.

 

4. 벽 제거하고 넓이를 구하기 위해 인접한 방과 방 번호가 다를 경우 HashMap에서 각 방 넓이를 가져와 더해준다.

 

 

 

 

내 코드

 

 

 

고려할 점

1. bfs를 사용할 것

2. HashMap을 사용하여 방에 따른 넓이를 담을 것

3. 벽 제거를 어떻게 하면 효율적으로 할지 생각할 것