학교 수업

오늘은 신호처리랑 객체지향 수업을 들었고 네트워크 프로그래밍에서 다룬 자바의 스트림을 복습했다. input/output stream, filter classes, file streams, buffered streams, data streams, character streams 내용을 리뷰했는데 양이 많아서 그렇지 열고-읽고-쓰고-닫기처럼 내용들이 서로 비슷비슷해 이해하기 수월했다. 내일은 thread 부분을 볼 예정이다.

PS

Bipartite 그래프인지를 판단하는 문제를 풀었다.
Bipartite 그래프란 간단히 얘기해서 그래프가 두 개의 집합으로 구성되어 있는데, 각 집합의 노드들이 다른 집합에 속한 노드들과만 연결이 되어있어야 하는 그래프이다. 즉 그래프에서 서로 adjacent한 노드들끼리의 색이 달라야 한다. 모든 노드를 방문해 edge를 검사하기 때문에 O(V+E)의 시간 복잡도를 갖는다. 어제 한 connected component의 개수를 구하는 것과 비슷했다.

Bipartite graph인지 판단하는 방법

  • DFS/BFS로 노드에 색 입히기
    • 노드에 색이 칠해지지 않은 경우 빨간색(임의)으로 칠한다.
    • 현재 노드에 색이 칠해져 있는 경우 다음에 방문한 노드의 색을 다른 색으로 칠한다.
void BFS() {
	queue<int> q;
	q.push(1);
	visit[1] = RED;

	while (!q.empty()) {
		int now = q.front();
		q.pop();
		int edgeSize = edge[now].size();
		for (int i = 0; i < edgeSize; i++) {
			int next = edge[now][i];
			if (visit[next] == -1) { // 아직 방문한 적이 없는 노드이면
				visit[next] = (visit[now] + 1) % 2; // now가 RED이면 next가 BLUE, now가 BLUE이면 next가 RED
				q.push(next);
			}
		}
	}
}

void DFS(int idx) {
	if (visit[idx] == -1) visit[idx] = RED;

	int edgeSize = edge[idx].size();
	for (int i = 0; i < edgeSize; i++) {
		int next = edge[idx][i];

		if (visit[next] == -1) { // 아직 방문한 적이 없는 노드이면
			visit[next] = (visit[idx] + 1) % 2; // now가 RED이면 next가 BLUE, now가 BLUE이면 next가 RED
			DFS(next);
		}
	}
}
  • 그래프가 bipartite인지 확인하기
    • 모든 노드들에 대해 edge 건너편에 있는 노드의 색이 달라야 한다. 즉 하나라도 다르면 bipartite graph가 아니다.
bool isBipartite() {
	for (int i = 1; i <= V; i++) {
		int edgeSize = edge[i].size();
		for (int j = 0; j < edgeSize; j++) {
			int next = edge[i][j];
			if (visit[i] == visit[next]) return false;
		}
	}
	return true;
}
  • 주의할 점
    주어진 그래프가 connected graph라는 보장이 없다. 이 경우 연결이 안 된 노드는 방문할 수 없기 때문에 모든 노드를 시작점으로 탐색을 해봐야 한다. 이미 색깔이 칠해져 있는 노드(이미 방문된 노드)라면 넘어가버리면 된다.
for (int i = 1; i <= V; i++) {
	if (visit[i] == -1) {
		DFS(i);
//		BFS();
	}
}