[백준, JAVA]14466번, 소가 길을 건너간 이유 6

문제 링크

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

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

 

접근 방법

BFS

BFS(너비 우선 탐색)은 아래 그림처럼 시작 노드에 인접한 노드를 모두 탐색한 후 인접한 노드를 기준으로 다시 인접한 노드를 찾아내는 것을 반복하여 탐색합니다.

시작 노드 탐색이 끝나면 인접했던 노드를 시작 노드로 생각하고 다시 탐색합니다.

출처: https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

더 자세한 내용은 아래 링크에 들어가서 확인해주시면 감사하겠습니다.

너비 우선 탐색 - 위키백과, 우리 모두의 백과사전

 

이 문제에 핵심

1. 소는 상하좌우 인접한 공간을 이동하며 길이 존재하면 이동시 길을 이용한다.

2. 소들이 길을 이용하지 않고 만날수 없는 쌍을 결과로 출력합니다.

 

브루트 포스로 모든 소의 쌍에 대하여 BFS탐색으로 길을 건너지 않고 만나는지 확인하였습니다.

 

BFS 탐색으로 길을 건너지 않고 만나는 소의 쌍을 결과로 출력합니다.

 

 

예제입력 1.

	Cow2(→)	Cow3(↓)
	(→)	Cow1(↑, ←)

 

(Cow1, Cow2) BFS 탐색

	Cow2(→)	Cow3(↓)
	(→)	Cow1(↑, ←)

 

Cow1에서는 모두 길을 건너야 하기 때문에 Cow2와 만날 수 있기 때문에 만족!

 

(Cow1, Cow3) BFS 탐색

	Cow2(→)	Cow3(↓)
	(→)	Cow1(↑, ←)

 

Cow1에서는 모두 길을 건너야 하기 때문에 Cow2와 만날 수 있기 때문에 만족!

 

(Cow2, Cow3) BFS 탐색

	Move	Move
	Cow2(→)	Cow3(↓)
	(→)	Cow1(↑, ←)

 

Cow2에서 ↑ - → - ↓순으로 이동하면 길을 건너지 않고 이동가능하기 때문에 만족 X!

 

지금까지 길을 건너며 만나는 소의 쌍은 2개입니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• String.charAt()을 이용해서 N, K, R과 소와 길에 위치에 대한 정보를 나누었습니다.
• 브루트 포스로 각 소의 쌍들이 길을 건너지 않고 만나는 소의 쌍이 만족하는지 확인하는  bfs함수를 실행하였습니다.
• 길을 건너지 않고 만나는 소의 쌍을 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• bfs는 각 소의 쌍이 길을 건너지 않고 만나는 소의 쌍을 만족하는지 BFS 탐색을 진행하는 함수입니다.

 

import java.util.*;
import java.io.*;

public class Main {
	//농장 위치 관련 클래스
    static class position{
        int x, y;
        public position(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    static int N,K,R;
    static ArrayList<position>[][] road;	//길 저장 배열
    static position[] cow;	//소 위치 저장 배열
    static int[] dx = {0, 0, -1, 1};	//상하좌우 x값 변경값
    static int[] dy = {-1, 1, 0, 0};	//상하좌우 y값 변경값
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());
        road = new ArrayList[N+1][N+1];
        cow = new position[K];
        for(int i=1;i<=N;i++){
            for(int j=1;j<=N;j++)
                road[i][j] = new ArrayList<>();
        }
        //길에 대한 정보 저장
        for(int i=0;i<R;i++){
            st = new StringTokenizer(br.readLine()," ");
            int r1 = Integer.parseInt(st.nextToken());
            int c1 = Integer.parseInt(st.nextToken());
            int r2 = Integer.parseInt(st.nextToken());
            int c2 = Integer.parseInt(st.nextToken());
            road[r1][c1].add(new position(c2,r2));
            road[r2][c2].add(new position(c1,r1));
        }
        //소에 대한 정보 저장
        for(int i=0;i<K;i++){
            st = new StringTokenizer(br.readLine()," ");
            int r1 = Integer.parseInt(st.nextToken());
            int c1 = Integer.parseInt(st.nextToken());
            cow[i] = new position(c1,r1);
        }

        int count = 0;
        //BFS탐색으로 길을 건너지 않고 만나는 소의 쌍인지 확인
        for(int i=0;i<K;i++){
            for(int j=i+1;j<K;j++){
                if(bfs(cow[i], cow[j]))	//길을 건너지 않고 만날 때
                    count++;
            }
        }
        bw.write(count +"");	//길을 건너지 않고 만나는 쌍의 개수 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //길을 건너지 않고 만나는 소의 쌍을 구하는 BFS 함수
    static boolean bfs(position startCow, position endCow){
        Queue<position> queue = new LinkedList<>();
        boolean[][] visited = new boolean[N+1][N+1];
        visited[startCow.y][startCow.x] = true;
        queue.add(startCow);
        while(!queue.isEmpty()){
            position cur = queue.poll();
            int x = cur.x;
            int y = cur.y;
            if(x==endCow.x && y == endCow.y)	//소끼리 만났을 때
                return false;
            for(int i=0;i<4;i++){
                int tempX = x + dx[i];
                int tempY = y + dy[i];
                if(tempX>0 && tempY>0 && tempX<=N && tempY<=N && !visited[tempY][tempX]){
                    boolean check = true;
                    for(int j=0;j<road[y][x].size();j++){	//길을 건널 때
                        if(road[y][x].get(j).x == tempX && road[y][x].get(j).y == tempY){
                            check = false;
                            break;
                        }
                    }
                    if(check){	//길이 아닐 때
                        visited[tempY][tempX] = true;
                        queue.add(new position(tempX,tempY));
                    }
                }
            }
        }
        return true;
    }
}