[BFS] 소가 길을 건너간 이유6

14466번: 소가 길을 건너간 이유 6 (acmicpc.net)

14466번: 소가 길을 건너간 이유 6

 

문제

소가 길을 건너간 이유는 그냥 길이 많아서이다. 존의 농장에는 길이 너무 많아서, 길을 건너지 않고서는 별로 돌아다닐 수가 없다.

존의 농장에 대대적인 개편이 있었다. 이제 작은 정사각형 목초지가 N×N (2 ≤ N ≤ 100) 격자로 이루어져 있다. 인접한 목초지 사이는 일반적으로 자유롭게 건너갈 수 있지만, 그 중 일부는 길을 건너야 한다. 농장의 바깥에는 높은 울타리가 있어서 소가 농장 밖으로 나갈 일은 없다.

K마리의 (1 ≤ K ≤ 100,K ≤ N2) 소가 존의 농장에 있고, 각 소는 서로 다른 목초지에 있다. 어떤 두 소는 길을 건너지 않으면 만나지 못 할 수 있다. 이런 소가 몇 쌍인지 세어보자.

 

입력

첫 줄에 N, K, R이 주어진다. 다음 R줄에는 한 줄에 하나씩 길이 주어진다. 길은 상하좌우로 인접한 두 목초지를 잇고, r c r′ c′의 형태 (행, 열, 행, 열)로 주어진다. 각 수는 1 이상 N 이하이다. 그 다음 K줄에는 한 줄의 하나씩 소의 위치가 행과 열로 주어진다.

출력

길을 건너지 않으면 만날 수 없는 소가 몇 쌍인지 출력한다.

 

구현

1.  가로 방향과 세로 방향의 길의 여부를 두 개의 배열로 관리 한다. 

 2. bfs를 이용하여 이동 가능한 공간을 같은 숫자로 세팅한다. 

while(!q.isEmpty()) {
			Pos p=q.poll();
			for(int i=0;i<4;i++) {
				int nx=p.x+dx[i];
				int ny=p.y+dy[i];
				
				if(nx<=0 || nx>N || ny<=0 || ny>N) continue;
				if(map[nx][ny]==map[p.x][p.y]) continue;
				 if(i==0) { 
					 if(road1[nx][ny]) continue;
				 }
				 else if(i==1) {
					 if(road1[p.x][ny]) continue;
				 }
				 else if(i==2) {
					 if(road2[nx][p.y]) continue;
				 }
				 else {
					 if(road2[nx][ny]) continue;
				 }
				map[nx][ny]=map[p.x][p.y]; //같은 숫자로 세팅
				q.add(new Pos(nx,ny));
			}
      }

실행 결과

==> 이를 통해 목초지 (2,2), (2,3)은 연결되어 있음을 알 수 있다. 

 

 

3. 길을 건너야 만날 수 있는 소의 쌍은 [(2,2),(3,3)], [(2,3),(3,3)] 두 가지가 있음을 알 수 있다.