방면적 넓히기 > 문제은행



알고리즘 자료구조2

1364 : 방면적 넓히기

제한시간: 1000 ms    메모리제한: 128 MB
해결횟수: 45 회    시도횟수: 126 회   



어느날 동훈이가 로또 1등에 당첨 되었다. 갑작스레 얻은 돈으로 무엇을 할까 고민하다. 유명한 아파트인 타이어펠리스에 입주를 하고자 하였다.

 

이사를 하기 전에 방을 살펴보던 도중 생각보다 방이 좁다고 느낀 동훈이는 자신이 거주하게 될 방을 최대한 크게 하기 위해서 벽을 허물고자 하였다. 하지만 많은 벽을 허물 경우 건물 자체에 무리가 생기기 때문에 타이어펠리스의 관리자는 벽을 딱 한 개만 허물 수 있도록 허가 하였다.

 

아파트가 제법 넓기 때문에 다음과 같은 설계 도면을 받아서 허물 벽을 결정하려고 한다. 아파트의 도면은 다음과 같이 주어지며 한 칸의 넓이는 1이며 ‘#’는 벽을 의미하며 ‘|’는 이미 뚫려 있는 곳을 의미한다. 방 하나는 벽으로 완전히 둘러싸인 공간을 말한다.

7ce7f2eba5731c8babe39036322897a0_1449816
 

위의 경우 기존의 방의 개수는 5개 이며, 가장 큰 방의 면적은 9이다. 여기서 (4,1)의 동쪽의 벽을 허물 경우 가장 큰 면적이 16으로 증가한다.

위와 같은 설계 도면에 대한 데이터가 주어졌을 때 처음의 방의 개수, 가장 큰 방의 면적, 그리고 벽 하나를 허물었을 경우의 면적과, 어느곳을 허물어야 하는지를 알아보는 프로그램을 작성하라.


입력은 첫 번째 줄에 아파트의 가로 길이 M, 세로 길이 N이 주어진다. M과 N은 1이상 50이하의 값이다. 두 번째 줄부터 N개의 줄에는 M개의 숫자가 주어지는데, 이는 설계도면의 데이터 이며 (1,1)부터 (N, M)까지의 칸에 대한 정보가 순서대로 주어진다. 각각의 칸에 대한 정보는 벽이 있는가에 대한 정보인데, 한 칸에 대해 다음과 같은 숫자의 합으로 표현이 된다.

1 : 서쪽(왼쪽)에 벽이 있을 경우 2 : 북쪽(위쪽)에 벽이 있을 경우 4 : 동쪽(오른쪽)에 벽이 있을 경우 8 : 남쪽(아래쪽)에 벽이 있을 경우

가령 (1,1)의 경우 서, 북, 남쪽에 벽이 있으므로 1+2+8 = 11 로 표현 된다.



입력된 설계도면에 대해 다음 값들을 출력한다. 첫 번째 줄 : 기존 방의 개수 두 번째 줄 : 가장 큰 방의 면적 세 번째 줄 : 벽을 하나 허물었을 경우 가장 큰 방의 면적 네 번째 줄 : 가장 큰 방을 얻기 위해서 허물 방의 위치와 그 방에서 본 벽의 방향 네 번째 줄의 경우 우선 세로위치, 가로위치를 빈칸을 두고 출력하고 빈칸 뒤에 허물벽의 방향에 대한 영어 대문자를 출력한다.(동, 서, 남, 북의 약자는 각각 'E', 'W', 'S', 'N' 와 같다.)

허물었을 경우 가장 큰 방을 얻을 수 있는 벽이 여러 개 있을 경우 그 벽을 허물수 있는 가장 서쪽의 방을 우선하여 선택한다. 가장 서쪽에 있는 방이 여러 개인 경우 가장 남쪽에 있는 방을 우선하여 선택한다.


7 4
11 6 11 6 3 10 6
7 9 6 13 5 15 5
1 10 12 7 13 7 5
13 11 10 8 10 12 13
5
9
16
4 1 E






HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.