섬 버스
시간 제한2초메모리 제한256 MB
각 격자 지도에서 직사각형 섬과 직선 다리 수를 세고 다리로 연결된 섬 묶음마다 버스 한 대씩 필요한 대수를 구합니다.
문제
한 해운 회사가 남태평양의 섬나라 여러 곳에 버스를 운행하려 한다. 나라 하나는 섬 여러 개로 이루어지고, 그중 일부는 다리로 이어져 있다. 비용을 줄이려고 회사는 버스를 가능한 한 적게 쓴다. 모든 섬에서 버스를 탈 수 있어야 하지만, 다리로 이어진 섬이 둘 이상이면 그 무리에는 버스를 한 대만 쓴다.
섬나라의 지도가 주어지면 섬의 수, 다리의 수, 그 나라에 필요한 버스의 최소 개수를 구하라.
입력
입력은 지도 여러 개로 이루어진다. 지도 하나는 문자로 채운 직사각형 격자이고, 행과 열이 각각 80 이하다. 연속한 두 지도 사이에는 빈 줄이 한 개 있다. 입력은 파일 끝에서 끝난다.
지도에는 ., X, #, B 네 문자만 나온다. 점은 바다이고 X와 #은 섬의 땅이다. B는 다리이며, X는 다리 한 개 이상이 끝나는 지점의 땅이다.
지도마다 섬이 한 개 이상 있고, 섬은 모두 땅으로 채운 직사각형이다. 서로 다른 두 섬은 위아래나 좌우로 맞닿지 않는다. 대각선으로만 닿아 있으면 버스가 건너가지 못한다.
지도마다 다리가 없을 수도 있고 여러 개 있을 수도 있으며, 다리는 가로나 세로로 놓인다. 다리 하나는 일직선으로 이어진 B 한 칸 이상이고, 양 끝의 X 칸이 속한 두 섬만 잇는다. B 칸이 다른 섬의 # 땅과 옆으로 맞닿아 있어도 그 섬까지 이어지지는 않는다. 다리끼리는 서로 교차하지 않고, 섬의 # 땅 위를 지나가지도 않는다. 같은 다리에 속하지 않는 한 B는 다른 B나 X와 맞닿지 않는다.
출력
지도마다 지도 번호를 출력하고, 이어서 섬의 수, 다리의 수, 필요한 버스의 수를 한 줄에 하나씩 출력한다. 연속한 두 지도의 출력 사이에는 빈 줄을 한 개 출력한다. 형식은 다음과 같다.
Map <번호>
islands: <개수>
bridges: <개수>
buses needed: <개수>