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

https://www.acmicpc.net/problem/14466

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

🌿 - 문제 설명

 

 

https://skygood95.tistory.com/38

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

이 분이 그림으로 설명을 잘해주셔서 참고하면 좋을 것 같다.

 

이 그림을 보고 문제를 풀면 더 이해가 잘 된다.

 

 

📌- 풀이

 

문제는 길을 건너지 않고 만날 수 있는 소들의 쌍을 구하는 것이 요점인데, BFS로 완전탐색을 하면 되기 때문에 그렇게 복잡하지 않아서 BFS는 문제가 없지만 길을 어떻게 표현할건지가 요점이었다.

 

ArrayList<Road>를 통해서 해당 좌표에 길이 있는지 확인을 하면 되게끔 만들었고,

 

BFS로 탐색을 하는 도중 길을 건너지 않았는데도 소를 마주치게 될 경우에는 카운트 값을 증가시켜주고

 

M(전체 소의수) - 1(본인)  - count를 통해서 

마주하지 못한 소를 세주고 이것을 소만큼 반복한다.

 

그리고 완전탐색이기 때문에 1번 소를 탐색할 때 3번소가 체크되고, 3번 소를 탐색할 때 1번 소가 체크되는 중복현상이 발생하므로 2를 나눠준 값을 출력하면 된다.

 

BFS의 확장이기 때문에 문제를 푸는 것에 딱히 어려움은 없었으나 문법적으로 조금 시간이 지체된 것이

 

if(road[go.x][go.y].contains(new Road(nx,ny)))

 

 

이렇게 해당 좌표값에 길이 포함되어있는지 체크를 해줘야하는데 포함이 되어있는데도 불구하고 계속 포함이 안되었다고 결과가 나와서 많은 시간을 허비한 것 같다.

 

 

이렇게 contains를 객체 비교로 사용하기 위해서는 아래의 클래스를 만들 때 equals를 오버라이딩해서 상위 클래스의 메소드를 재정의 해줘야 제대로 비교가 가능하다.

 

class Road{
    int x;
    int y;
    Road(int x , int y){
        this.x = x;
        this.y = y;
    }

    @Override // ------> 이 부분을 넣어줘야 contains를 할 때 정확한 값이 나온다.
    public boolean equals(Object obj) {
        Road node = (Road) obj;

        return this.x == node.x && this.y == node.y;
    }
}

 

참고

https://hianna.tistory.com/556

[Java] List에 특정 값이 포함되어 있는지 확인하기

 

🔥 - Java 전체 코드

 

package BFS.G4_14466_소가길을건너는이유6;

import java.io.*;
import java.sql.Array;
import java.util.*;

public class Main {
        public static int N,M,R,result=0;
        static int[][] map;
        static ArrayList<Road>[][] road;
        static int[] dx = {0,0,1,-1};
        static int[] dy = {1,-1,0,0};

    public static void main(String[] args) throws IOException {
        //BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new FileReader("src/input.txt"));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(st.nextToken()); // 크기
        M = Integer.parseInt(st.nextToken()); // 소 마리 수
        R = Integer.parseInt(st.nextToken()); // 길 수

        map = new int[N+1][N+1];
        road = new ArrayList[N+1][N+1];

        for(int i=1;i<N+1;i++){
            for(int j=1;j<N+1;j++){
                road[i][j] = new ArrayList<>();
            }
        }



        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());
            road[x1][y1].add(new Road(x2,y2));
            road[x2][y2].add(new Road(x1,y1));
        }

        Queue<Road> que = new LinkedList<>();
        for(int i=0;i<M;i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            que.add(new Road(a,b));
            map[a][b] = 1;
        }

        bfs(que);


        System.out.println(result/2);




    }
    public static void bfs(Queue<Road> que){
        while(!que.isEmpty()){
            Road cow = que.poll();
            Queue<Road> next = new LinkedList<>();
            boolean[][] visited = new boolean[N+1][N+1];
            next.add(cow);
            visited[cow.x][cow.y] = true;
            int count =0;
            while(!next.isEmpty()){
                Road go = next.poll();
                for(int i=0;i<4;i++){
                    int nx = go.x+dx[i];
                    int ny = go.y+dy[i];
                    if(0<nx && nx < N+1 && 0<ny && ny<N+1 && !visited[nx][ny] ){

                        if(road[go.x][go.y].contains(new Road(nx,ny))){
                           continue;
                        }
                        if(map[nx][ny] == 1){
                            count++;
                        }
                        visited[nx][ny] = true;
                        next.add(new Road(nx,ny));
                    }
                }

            }
            result += ((M - 1) - count);

        }
    }



}
class Road{
    int x;
    int y;
    Road(int x , int y){
        this.x = x;
        this.y = y;
    }

    @Override
    public boolean equals(Object obj) {
        Road node = (Road) obj;

        return this.x == node.x && this.y == node.y;
    }
}