백준 14466 <소가 길을 건너간 이유 6>

문제를 이해하는데 시간이 오래 걸렸던 문제

기본적으로 이렇게 소와 다리가 위치하고 있다.

주황색 소에서 하늘색 소로 가는 경우는 다리를 이용하지 않고 이렇게 이동할 수 있다.

 

그러나 주황색 소에서 초록색 소를 가려면 무조건 다리를 건너야 한다

파란색 소에서 초록색 소도 마찬가지이다.

 

이렇게 되면 다리를 건너야 하는 소들은 총 2쌍이다.

 

그러므로 이 문제는 각각의 소에서 다리를 이용하지 않고 다른 소들을 방문 할 수 있냐? 하는 문제이다.

 

결과적으로 쌍을 구하는 것이기 때문에 자기보다 뒤에 있는 소들만 계산해주고 앞에 있는 소들은 계산할 필요가 없다.

 

문제 풀이

1. 각각의 소에서 BFS를 해서 다리를 이용하지 않은 완전 탐색을 한다.
2. 자신보다 이후에 위치한 소들이 방문 되지 않았다면 count를 증가시킨다.

결과적으로 완전 탐색인 문제이다.

 

소가 총 100마리 있으므로 각각의 BFS를 하는데 걸리는 시간은 10000*100=100만

그리고 이후의 소들을 계산하는 수 100*(1+2+3+4+...+100) 대략 100*100*100=100만

 

두 개의 합은 200만이므로 시간은 프리 하게 패스!

 

여기서 나는 boolean형 visit[][][][]을 사용해서 불필요한 메모리를 사용했지만 각각의 hash맵이다 arraylist를 사용하면 메모리를 줄일 수 있다.

 

전체 코드

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static boolean visit[][][][],check[][];
	static int n, k, r, result,dir[][]= {{-1,0},{0,1},{1,0},{0,-1}};
	static Point p[];

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		r = Integer.parseInt(st.nextToken());
		visit = new boolean[n + 1][n + 1][n + 1][n + 1];
		for (int i = 0; i < r; i++) {
			st = new StringTokenizer(br.readLine());
			int x1 = Integer.parseInt(st.nextToken());
			int y1 = Integer.parseInt(st.nextToken());
			int x2 = Integer.parseInt(st.nextToken());
			int y2 = Integer.parseInt(st.nextToken());
			visit[x1][y1][x2][y2] = true;
			visit[x2][y2][x1][y1] = true;
		}
		p = new Point[k];
		for (int i = 0; i < k; i++) {
			st = new StringTokenizer(br.readLine());
			p[i] = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
		}
		for (int i = 0; i < k; i++) {
			check = new boolean[n + 1][n + 1];
			bfs(p[i].x, p[i].y);
			for (int j = i + 1; j < k; j++) {
				if (!check[p[j].x][p[j].y]) {
					result++;
				}
			}
		}
		System.out.println(result);

	}
	private static void bfs(int x, int y) {
		// TODO Auto-generated method stub
		Queue<Point> q=new LinkedList<Point>();
		q.add(new Point(x,y));
		check[x][y]=true;
		while(!q.isEmpty()) {
			Point next=q.remove();
			for(int i=0;i<4;i++) {
				int x1=next.x+dir[i][0];
				int y1=next.y+dir[i][1];
				if(x1<=0||x1>n||y1<=0||y1>n)
					continue;
				if(visit[next.x][next.y][x1][y1]||check[x1][y1])
					continue;
				check[x1][y1]=true;
				q.add(new Point(x1,y1));
			}
		}
		
	}

}