https://www.acmicpc.net/problem/14466
14466번: 소가 길을 건너간 이유 6
첫 줄에 N, K, R이 주어진다. 다음 R줄에는 한 줄에 하나씩 길이 주어진다. 길은 상하좌우로 인접한 두 목초지를 잇고, r c r′ c′의 형태 (행, 열, 행, 열)로 주어진다. 각 수는 1 이상 N 이하이다.
www.acmicpc.net
🌿 - 문제 설명

https://skygood95.tistory.com/38
백준 14466 <소가 길을 건너간 이유 6>
문제를 이해하는데 시간이 오래 걸렸던 문제 기본적으로 이렇게 소와 다리가 위치하고 있다. 주황색 소에서 하늘색 소로 가는 경우는 다리를 이용하지 않고 이렇게 이동할 수 있다. 그러나 주황
skygood95.tistory.com
이 분이 그림으로 설명을 잘해주셔서 참고하면 좋을 것 같다.


이 그림을 보고 문제를 풀면 더 이해가 잘 된다.
📌- 풀이
문제는 길을 건너지 않고 만날 수 있는 소들의 쌍을 구하는 것이 요점인데, 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에 특정 값이 포함되어 있는지 확인하기
List에 특정 값이 포함되어 있는지 확인하는 방법입니다. contains() indexOf() 반복문 Iterator를 사용한 반복문 Stream API 1. contains() 코드 import java.util.ArrayList; import java.util.Arrays; import java.util.List; public cla
hianna.tistory.com
🔥 - 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;
}
}
https://www.acmicpc.net/problem/14466
14466번: 소가 길을 건너간 이유 6
첫 줄에 N, K, R이 주어진다. 다음 R줄에는 한 줄에 하나씩 길이 주어진다. 길은 상하좌우로 인접한 두 목초지를 잇고, r c r′ c′의 형태 (행, 열, 행, 열)로 주어진다. 각 수는 1 이상 N 이하이다.
www.acmicpc.net
🌿 - 문제 설명

https://skygood95.tistory.com/38
백준 14466 <소가 길을 건너간 이유 6>
문제를 이해하는데 시간이 오래 걸렸던 문제 기본적으로 이렇게 소와 다리가 위치하고 있다. 주황색 소에서 하늘색 소로 가는 경우는 다리를 이용하지 않고 이렇게 이동할 수 있다. 그러나 주황
skygood95.tistory.com
이 분이 그림으로 설명을 잘해주셔서 참고하면 좋을 것 같다.


이 그림을 보고 문제를 풀면 더 이해가 잘 된다.
📌- 풀이
문제는 길을 건너지 않고 만날 수 있는 소들의 쌍을 구하는 것이 요점인데, 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에 특정 값이 포함되어 있는지 확인하기
List에 특정 값이 포함되어 있는지 확인하는 방법입니다. contains() indexOf() 반복문 Iterator를 사용한 반복문 Stream API 1. contains() 코드 import java.util.ArrayList; import java.util.Arrays; import java.util.List; public cla
hianna.tistory.com
🔥 - 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;
}
}