아주정은's 릴상

이문제는 생각이 많이 필요한 문제였다. 왜냐하면 문제 자체를 이해하지 못하였기 때문이다.

나는 이분그래프라고해서 그래프중에 트리를 말하는줄알고 처음에는 사이클이 존재하는지 여부를 따졌었다. 그래도 예제는 통과할 수 있었는데, 계속 틀렸다고 나와서 결국 구글에 검색을 하였다........꾸준함님의 블로그를 참조하였다.....

거의 카피했다고 봐도 무방;;;;; 그래도 마지막 자존심으로 변수이름이나....내가 쓰던 패턴들은 그대로 썻다;;; 이것까지 바꾸는건 좀 그랬다...

꾸준함님이 코드를 워낙 잘짜놔서 현타가 씨게 왔다;;

이분 그래프란 그래프에서 노드들을 두 집합으로 나눴을때 같은 집합에 있는 노드들끼리 연결된 것이 없을때 이분그래프라고 할 수 있다.

그래서 BFS든 DFS든 완전탐색을 통해서 모든 노드들을 탐색하면서 각각 노드들에 색깔을 입혀준다. 그 다음 모든 노드를 돌면서 각각의 노드에 연결된 이웃들이 자신과 색깔이 같은지 판단을 하면된다.

소스코드는 아래 첨부한다. 나중에 필히 다시 풀어볼 문제이다. 왜냐하면 어디선가 또 나올것같은 문제이기 때문이다.

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> board;
vector<int> vis; // 노드 방문여부 및 색깔

void DFS(int input, int color) {
	vis[input] = color;
	for (int i = 0; i < board[input].size(); i++) {
		if (vis[board[input][i]] == 0) {
			DFS(board[input][i], 3 - color);
		}
	}
}

bool is_disparity() {
	
	for (int i = 0; i < vis.size(); i++) {
		for (int j = 0; j < board[i].size(); j++) {
			if (vis[i] == vis[board[i][j]]) return false;
		}
	}
	return true;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int K, V, E; // 케이스 갯수, 정점 갯수, 간선 갯수
	int a, b;
	cin >> K;

	while (K--) {
		cin >> V >> E;

		board.assign(V+1, vector<int>(0,0));// vector 초기화
		vis.assign(V+1, 0);
		
		while (E--) {
			cin >> a >> b;
			board[a].push_back(b);
			board[b].push_back(a);
		} // 그래프 그리기

		for (int i = 1; i < V + 1; i++) {
			if (vis[i] == 0) {
				DFS(i,1);
			}
		} // 컬러 다 입혔다.
		
		if (is_disparity()) {
			cout << "YES" << endl;
		}
		else {
			cout << "NO" << endl;
		}
		
	}
}

오늘은 토요일,,, 어제 술을 너무 많이 먹고 실수를 해서 하루종일 기부니가 좋지않은 날이다.....

진짜 영어로 욕하고 싶은 날이다. 스윙스 맹키로;; 여 쉿! 음~ 여기까지

생각도 없앨겸 문제를 한문제 푸는데 문제를 풀면서도 계속 생각이 나고 마음이 진정이 되지 않았다.

하지만 문제는 1번 시도했는데 맞아버렸다;;;;; 그래도 기쁘지가 않았다. 앞으로 실수는 노노놉!!

이제 문제얘기로 돌아와서 이거 문제의 글이 제법 길어서 집중해서 읽어봤는데, 그냥 BFS이용해서 모두 탐색하면 되는것 같았다. 

치즈가 놓여있지 않은 외벽부터 시작해서 0으로 되어있는 곳을 모두 탐색을 한다. 그리고 공기와 붙어있는 1을 0으로 바꿔준다. 이때 갱신하면서 오류가 날수있기  때문에 copy_board를 만들어줬는데, 흠 꼭 필요했나 싶기도 하다. 방문을 했는지 여부를 이용해서 해도 될것같았기 때문이다.

소스코드를 참고하고 언제나 피드백은 환영이다.

무엇보다 실수를 줄이자!! 쿄,,,,,,,,,,,,,,,,쿄

#include <iostream>
#include <queue>

using namespace std;

struct Que {
	int x;
	int y;
};

int board[102][102];
int copy_board[102][102];
bool vis[102][102];

int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };

void board_initialize() {
	for (int i = 0; i < 102; i++) {
		for (int j = 0; j < 102; j++) {
			board[i][j] = 0;
		}
	}
}

void vis_initialize() {
	for (int i = 0; i < 102; i++) {
		for (int j = 0; j < 102; j++) {
			vis[i][j] = false;
		}
	}
}


void copy_initialize() {
	for (int i = 0; i < 102; i++) {
		for (int j = 0; j < 102; j++) {
			copy_board[i][j] = 0;
		}
	}
}

void board_to_copy(int a, int b) {
	for (int i = 0; i < a; i++) {
		for (int j = 0; j < b; j++) {
			copy_board[i][j] = board[i][j];
		}
	}
}

bool mission_success(int a, int b) {
	bool success = true;
	for (int i = 0; i < a; i++) {
		for (int j = 0; j < b; j++) {
			if (board[i][j] == 1) {
				success = false;
				break;
			}
		}
		if (!success) break;
	}
	return success;
}



int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int a, b;
	int time = 0;
	int count = 0;

	cin >> a >> b;

	board_initialize();
	copy_initialize();

	for (int i = 0; i < a; i++) {
		for (int j = 0; j < b; j++) {
			cin >> board[i][j];
		}
	}


	while (!mission_success(a,b)) {
		board_to_copy(a, b);
		vis_initialize();

		queue<Que> Q;
		Q.push({ 0,0 });
		vis[0][0] = true;

		while (!Q.empty()) {
			auto cur = Q.front();
			Q.pop();

			for (int i = 0; i < 4; i++) {
				int nx = cur.x + dx[i];
				int ny = cur.y + dy[i];

				if (nx < 0 or nx >= a or ny < 0 or ny >= b) continue;
				if (copy_board[nx][ny] == 0 and vis[nx][ny] == false) {
					Q.push({ nx,ny });
					vis[nx][ny] = true;
				} else if (copy_board[nx][ny] == 1 and vis[nx][ny] == false) {
					board[nx][ny] = 0;
					vis[nx][ny] = true;
				}
			}
		}
		time++;
	}

	for (int i = 0; i < a; i++) {
		for (int j = 0; j < b; j++) {
			if (copy_board[i][j] == 1) {
				count++;
			}
		}
	} // 마지막에 남은 치즈 칸 수 세기

	cout << time << endl << count << endl;
	
}
//shout out to lynnnnnnnnn!

근무하면서 커밋 한번 하면 쉬는거 국룰이라길래 쉬면서 촌수계산이라는 문제를 풀었다.

이 문제들은 현정이가 만들어놓은 문제집에서 골라 푸는건데 그 문제집에 있는 100문제를 다 풀고싶다.

단순히 코테를 준비하는 것이 아니라 재밌다 ㅋㅋㅋ 취미가 문제풀이가 됐으면 좋겠다.

일단 촌수계산은 어릴때부터 많이해봐서 문제 자체는 어렵지 않았다. 그래프를 그릴수만있다면

진짜 한조각 케익이라고 생각했다. 막상 그래프를 그리고 어떻게 돌아야 효율적일까 하는 고민을 하게되었다.

나는 queue를 이용해서 BFS방식을 사용하였다.

촌수를 계산할 두명중 한명을 큐에 넣어주고 그 한사람과 연결된 모든 사람을 큐에 집어넣는다.

그리고 방문했다는 표시를 해준다. 그렇게 그래프를 돌다가 찾는 사람을 발견하면 관계를 출력해주면 된다.

한 계층씩 내려갈때마다 time을 늘려줌으로써 몇 촌인지 계산한다.

싸이월드에서는 너와 나는 1촌이었는데, 지금 우리는 몇촌일까?

삼시세끼 어촌편 보러가야짓,, 쵼쵼!

#include <iostream>
#include <queue>

using namespace std;

struct Que {
	int x;
	int time;
};

int board[102][102];
bool vis[102];

void initialize() {
	for (int i = 0; i < 102; i++) {
		vis[i] = false;
		for (int j = 0; j < 102; j++) {
			board[i][j] = 0;
		}
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n; //사람 수
	int a, b; // 촌수계산 두사람
	int m;
	int x, y;
	int relation = -1;
	cin >> n >> a >> b >> m;

	initialize();

	while (m--) {
		cin >> x >> y;
		int i = 0;
		while (board[x][i] != 0) {
			i++;
		}
		board[x][i] = y;

		int j = 0;
		while (board[y][j] != 0) {
			j++;
		}
		board[y][j] = x;
	} // 그래프 형성
	
	queue<Que> Q;
	Q.push({ a,0 });
	vis[a] = true;
	while (!Q.empty()) {
		auto cur = Q.front();
		Q.pop();
		int i = 0;
		while (board[cur.x][i] != 0) {
			int neighbor = board[cur.x][i];
			if (neighbor == b) {
				relation = cur.time + 1;
				goto ijsilver;
			}
			if (vis[neighbor] == false) {
				Q.push({ board[cur.x][i],cur.time + 1 });
				vis[board[cur.x][i]] = true;
			}
			i++;
		}
	}

ijsilver:
	cout << relation << endl;
	return 0;
}

//양방향 간선을 통해서 그래프를 그리자.

회사와서 한문제 푸는데 이문제는 제법 고민을 많이했던것같다.

가장 기본에 충실한 문제 같으면서도, 막상 어떻게 노드들의 구현을 해야할지 의문이 많이 들었다.

배열로 board를 만들어야할까 vector로 만들어야할까 고민도 굉장히 많이했다.

DFS를 구현할때는 stack을 쓸까 재귀를 쓸까도 고민을 많이했는데, 스택보다 재귀가 편하다고 판단되어 재귀를 사용하였다. 어짜피 DFS는 한곳 쭉~~~파다가 막히면 돌아오는 개념이기 때문에 재귀가 그 개념과 부합되는 이미지라고 판단했기 때문이다.

BFS는 평소 하던대로 queue를 사용하였다. 방문 여부를 묻고 큐에 넣고 출력을 해주었다.

내 소스코드에서 큐는 하나 선언했다. 코드 제출도 1번만 하였다. 이건 말그대로 당구장 아니지만 원큐였다.

참고하고 댓글로 피드백 주면 감사하겠습니다.

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

int board[1002][1002];
bool vis[1002];

void dfs(int v) {

	cout << v << " ";
	vis[v] = true;
	int i = 0;
	while (board[v][i]) {
		if (vis[board[v][i]] == false) {
			dfs(board[v][i]);
		}
		i++;
	}
}

void bfs(int v) {
	queue<int> Q;
	Q.push(v);
	vis[v] = true;
	
	while (!Q.empty()) {
		int cur = Q.front();
		Q.pop();
		cout << cur << " ";
		int i = 0;
		while (board[cur][i]) {
			int node_num = board[cur][i];
			if (vis[node_num] == false) {
				Q.push(node_num);
				vis[node_num] = true;
			}
			i++;
		}
	}
}

void board_initialize() {
	for (int i = 0; i < 1002; i++) {
		for (int j = 0; j < 1002; j++) {
			board[i][j] = 0;
		}
	}
}

void vis_initialize() {
	for (int i = 0; i < 1002; i++) {
		vis[i] = false;
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int N, M, V;
	int a, b;
	cin >> N >> M >> V;
	
	//배열 초기화
	board_initialize();
	vis_initialize();
	
	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		int j = 0, k = 0;
		while (board[a][j]) {
			j++;
		} // 간선 넣을 곳 찾기
		board[a][j] = b;

		while (board[b][k]) {
			k++;
		}
		board[b][k] = a;
	} // 양방향 노드 간선 추가하기


	for (int i = 1; i <= N; i++) {
		int j = 0;
		while (board[i][j]) {
			j++;
		}
		sort(board[i], board[i]+j);
	} // board 오름차순으로 정렬

	dfs(V);
	cout << endl;
	vis_initialize(); // 방문 여부 초기화
	bfs(V);
}

11달 전에도 풀었고 6달 전에도 풀었던 문제를 오랜만에 감좀 익힐겸 다시 풀어봤다.

역시 basic했다고 할 수 있다. 뭐 원샷 원킬했다!

BFS오랜만에 해봤는데 예전에 외웠던 코드들이 아직도 기억에 남아있는것같다.

앞으로도 까먹지않게 종종 연습하고 진도를 쭉쭉 나가야겠다.

이거 코드는 보면 바로 이해가 갈 것이다.

#include <iostream>
#include<queue>

struct Que {
	int x;
	int y;
};



int board[501][501];
bool vis[501][501];
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };



using namespace std;

int main()
{
    ios::sync_with_stdio(0);
	cin.tie(0);
	int a, b;
	cin >> a >> b;//가로 세로길이

	for (int i = 0; i < a; i++) {
		for (int j = 0; j < b; j++) {
			cin >> board[i][j];
		}
	}
	queue<Que> Q;
	Que q;
	int count = 0;
	int max = 0;
	int area = 0;
	for (int i = 0; i < a; i++) {
		for (int j = 0; j < b; j++) {
			if (board[i][j] == 1 && vis[i][j] == false) {
				Q.push({ i, j });
				vis[i][j] = true;
				count++;
			}

			while (!Q.empty()) {
				q = Q.front();
				Q.pop();
				
				area++;

				
				for (int k = 0; k < 4; k++) {
					if (q.x + dx[k]<0 or q.x + dx[k]>=a or q.y + dy[k]<0 or q.y + dy[k]>=b)continue;
					if (board[q.x + dx[k]][q.y + dy[k]] == 1 && vis[q.x + dx[k]][q.y + dy[k]] == false) {
						Q.push({q.x + dx[k],q.y + dy[k]});
						vis[q.x+dx[k]][q.y+dy[k]] = true;
					}
				}
			}
			if (max < area) {
				max = area;
			}
			area = 0;


		}
	}
	cout << count << endl << max;

}