✅문제
✅문제 풀이
관계가 A-B, B-C, C-D, D-E가 있는지 확인하는 문제이다.
모두다 한번씩 확인하려면 for문이 5번 돌아가기 때문에 A-B, C-D를 모두 한번씩 돌려서 for문을 2번만 사용하고
B-C, D-E가 있는지 한번씩만 확인하면 효율적으로 문제를 풀 수 있다.
밑에 풀이는 Pair, Graph 클래스를 사용하여 문제를 풀었다.
Lombok... 있다없으니까 소중함을 다시 느낍니다... ㅠㅠ
✅Code
public class Beak13023 {
public static class Pair{
private int x;
private int y;
public Pair(int x, int y){
this.x = x;
this.y = y;
}
public int getX() {
return x;
}
public int getY(){
return y;
}
}
public static class Graph {
private List<List<Integer>> arrays;
private List<Pair> edges;
private int size;
public Graph(int size) {
arrays = new ArrayList<>();
edges = new ArrayList<>();
this.size = size;
for (int i = 0; i < size; i++) {
List<Integer> row = new ArrayList<>();
for (int j = 0; j < size; j++) {
row.add(0);
}
arrays.add(row);
}
}
public void addEdge(int i, int j) {
arrays.get(i).set(j, 1);
arrays.get(j).set(i, 1);
edges.add(new Pair(i,j));
}
public boolean check(int i, int j){
return arrays.get(i).get(j) == 1;
}
public List<List<Integer>> getArrays() {
return arrays;
}
}
public static class GraphService {
private Graph graph;
public GraphService(Graph graph) {
this.graph = graph;
}
private boolean check() {
List<List<Integer>> arrays = graph.getArrays();
for (Pair firstPair : graph.edges) {
for (Pair secondPair : graph.edges) {
int a = firstPair.getX();
int b = firstPair.getY();
int c = secondPair.getX();
int d = secondPair.getY();
if (a == b || a == c || a == d || b == c || b == d || c == d)
continue;
if (!graph.check(b,c))
continue;
List<Integer> filteredArrays = new ArrayList<>();
for (int i = 0; i < arrays.get(d).size(); i ++){
if(arrays.get(d).get(i) == 1)
filteredArrays.add(i);
}
for (Integer e : filteredArrays) {
if (a == e || b == e || c == e || d == e)
continue;
return true;
}
}
}
return false;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
Graph graph = new Graph(n);
for (int i = 0; i < m ; i++) {
st = new StringTokenizer(br.readLine());
graph.addEdge(
Integer.parseInt(st.nextToken()),
Integer.parseInt(st.nextToken())
);
}
GraphService graphService = new GraphService(graph);
if (graphService.check()) {
System.out.println("1");
} else {
System.out.println("0");
}
}
}
'알고리즘 > 브루트포스' 카테고리의 다른 글
[백준] 14500번 : 테트로미노 풀이(python) (1) | 2023.10.17 |
---|---|
[백준] 10974번 : 모든 순열 풀이(python) (2) | 2023.10.14 |
[백준] 1476번 : 날짜 계산 풀이(python) (0) | 2023.10.11 |
[백준] 2309번 : 일곱 난쟁이 풀이(python) (1) | 2023.10.11 |