[백준, BFS, JAVA] P.1707 이분 그래프

어후;; 20번 틀리고 21번째에 드디어 해결했네요... 알고보니 로직은 그럭저럭 맞는것 같았으나 BFS에 대한 공부 부족과 객체 지향 활용을 못한 원인이 가장 컸던 것 같습니다.. 차근차근 어떤 문제 상황에 부딪혔고 해결했는지 끄적여 보겠습니다. 저는 고수분들이랑 다르게 간단하고
명료하게 추상화해서 몇줄 안되는 코드로는 못짜서 코드가 길고 좀 보기 싫습니다.. 그냥 저만의 회고시간입니다..

• 클래스 정의
  우선 Vertax 클래스를 설계했습니다.

class Vertax {
	private int index;
	private int color; // -1 색없음, 0 빨 1 파
	private HashSet<Vertax> connectedEdges; // 해당 정점과 연결된 정점들을 저장 하기 위한 자료구조

	public Vertax(int index) {
		this.index = index;
		color = -1;
		connectedEdges = new HashSet<>();
	}
    
    // getter, setter는 코드 길이상 생략했습니다.
    // ...
}

정점의 위치를 표시하는 index, 색깔을 나타내는 color, 해당 정점과 연결된 다른 정점들을 저장한 connectedEdges(Vertax가 맞는듯..)

public class Main {
	public static int color;
	public static int K, V, E;
	public static StringBuffer sb = new StringBuffer();
	public static boolean result = false; // 결과값 true면 YES false면 NO
	public static Queue<Vertax> vertaxQueue; // bfs탐색을 위한 정점 큐

정적 변수들입니다. 저 위에 color를 지워도 되지만 굳이 넣은 이유는 저거 때문에 20번, 샐 수도 없는 시간을 허비했기 때문입니다.
(저거 때문이라기 보다는 그냥 문제 제대로 이해 못하고 무작정 코딩부터하고 제대로 구현 못한 저의 책임..)
아래의 코드에서 어떤 실수를 했는지 적겠습니다.
main 함수입니다. 주석에 번호를 표시해놨습니다.

public static void main(String[] args) {
		Scanner scr = new Scanner(System.in);
		List<Vertax> vertaxVector = null; // 정점을 모아놓은 벡터들 Vertax.index-1의 위치에 각각 저장됩니다.

		K = scr.nextInt();

		for (int i = 0; i < K; i++) {
			V = scr.nextInt();
			E = scr.nextInt();
			color = 0;
			result = true; // 1
			vertaxQueue = new LinkedList<Vertax>(); 

			vertaxVector = new ArrayList<>();

			for (int n = 1; n <= V; n++) {
				Vertax vertax = new Vertax(n);
				vertaxVector.add(vertax);
			}

			for (int n = 1; n <= E; n++) { // 2
				int v1Index = scr.nextInt();
				int v2Index = scr.nextInt();

				Vertax v1 = vertaxVector.get(v1Index - 1);
				Vertax v2 = vertaxVector.get(v2Index - 1);

				v1.getConnectedEdges().add(v2);
				v2.getConnectedEdges().add(v1);
			}

			for (Vertax v : vertaxVector) { // 3
				if (v.getColor() != -1) { 
					continue;
				}
				
				v.setColor(color);
				vertaxQueue.add(v);

				while (!vertaxQueue.isEmpty()) {
					
					Vertax element = vertaxQueue.poll();
					if (!bfsVertax(element)) {
						result = false;
						break;
					}
				}
			}

			if (result) {
				sb.append("YES\n");
			} else {
				sb.append("NO\n");
			}
		}

		System.out.println(sb.toString());
	}

1. 결과값 및 큐와 벡터를 테스트 케이스마다 초기화 합니다.
2. Edge를 입력받아 각 정점끼리의 양방향 연결을 위해 구현한 부분입니다.
3. BFS를 시작하는 부분입니다. 저기서 정적 변수 color로 처음 시작하는 값을 초기화해주는데 color값이 딱히 필요없습니다. 오히려
   저것 때문에 더 헷갈렸습니다. 이분 그래프는 서로 아예 연결되지 않은 정점간에는 컬러 값이 어떤 값이든 상관 없기 때문입니다.
   그래서 그냥 0 내지 1 아무거나 넣어도 상관없습니다.

bfs 구현 함수입니다.

public static boolean bfsVertax(Vertax vertax) {
		Iterator<Vertax> itr = vertax.getConnectedEdges().iterator();

		while (itr.hasNext()) {
			Vertax v = itr.next();
			if (v.getColor() != -1 && vertax.getColor() == v.getColor()) {
				return false;
			}

			if (v.getColor() == -1) {
//				v.setColor( color + 1 % 2);
				v.setColor(vertax.getColor() + 1 % 2);
				vertaxQueue.add(v);
			}
		}
		
//		color = color + 1 % 2;
		return true;
	}

주석의 코드가 시간 낭비한 코드입니다. 위의 말한 이분그래프의 특성과 Vertax 클래스가 있는데 굳이 외부 color 값을 조건에 따라 바꿔주면서 짤필요가 없죠 BFS를 따라서 현재 vertax의 컬러에 1을 더하고 2를 %연산 해준 값을 저장해주어 해결했습니다. 참 기초도 없고 허튼 짓만 골라서 한 느낌이네요... 프레임워크나 간단한 비지니스 로직 개발만 추구해오던 인생이 알고리즘에서 재판 받는 기분입니다. 앞으로
꾸준히 정진하겠습니다..