2653 음악프로그램
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, M, n;
vector<vector<int>> adj, temp;
vector<int> seen, order;
void makeTree() {
adj = vector<vector<int>>(N + 1, vector<int>(N + 1, 0));
for (int i = 0; i < M; i++) {
for (int j = 0; j < temp[i].size() - 1; j++) {
adj[temp[i][j]][temp[i][j + 1]] = 1;
}
}
}
void dfs(int here) {
seen[here] = 1;
for (int i = 0; i < adj[here].size(); i++) {
if (adj[here][i] && !seen[i]) dfs(i);
}
order.emplace_back(here);
}
void dfsAll() {
seen = vector<int>(N + 1, 0);
for (int i = 1; i <= N; i++) {
if (!seen[i]) dfs(i);
}
reverse(order.begin(), order.end());
for (int i = 0; i < order.size(); i++) {
for (int j = i + 1; j < order.size(); j++) {
if (adj[order[j]][order[i]]) {
cout << 0;
return;
}
}
}
for (int i : order) {
cout << i << '\n';
}
}
int main() {
cin >> N >> M;
for (int j = 0; j < M; ++j) {
cin >> n;
vector<int> v;
int i;
while (n--) {
cin >> i;
v.emplace_back(i);
}
temp.emplace_back(v);
}
makeTree();
dfsAll();
}📍 위상 정렬 문제
인접 행렬 사용
- 위상 정렬에서 사이클인지 아닌지 확인하는 부분에서 인접 리스트를 사용하면 삼중 for문을 사용해야함!
- dfs 함수 내에서 방문했는지 아닌지(
!visited[i])뿐만 아니라 인접한지 아닌지(adj[i][j])도 확인해야함
벡터 크기 초기화 : vector<int> v(size, value);
이차원 벡터 크기 초기화 : vector<vector<int>> v2(size, vector<int>(size2, value))
14926 Not Equal
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int N;
vector<vector<int>> adj;
vector<string> ans;
void getEulerCircuit(int here) {
for (int there = 0; there < N; there++) {
if (adj[here][there]) {
adj[here][there]--;
adj[there][here]--;
getEulerCircuit(there);
}
}
string s = "a" + to_string(here + 1);
ans.emplace_back(s);
}
int main() {
cin >> N;
adj = vector<vector<int>>(N + 1, vector<int>(N + 1, 1));
for (int i = 0; i < N; i++) {
adj[i][i] = 0;
}
getEulerCircuit(0);
reverse(ans.begin(), ans.end());
for (string s : ans) {
cout << s << " ";
}
}📍 오일러 서킷 문제
가만 보니 reverse 함수를 안 쓰고 걍 .. for(int i = N-1 ; i >= 0 ; i--) 로 했어도 됐겠네
❌ 벡터 초기화는 전역에서 하면 안됨(아마 변수 N을 사용해서 그런듯)
2606 바이러스
#include <iostream>
#include <vector>
using namespace std;
int C, N, cnt = 0;
vector<vector<int>> adj;
vector<int> visited;
void dfs(int here) {
visited[here] = 1;
for (int i = 1; i <= C; i++) {
if (adj[here][i] && !visited[i]) {
dfs(i);
cnt++;
}
}
}
int main() {
cin >> C >> N;
adj = vector<vector<int>>(C + 1, vector<int>(C + 1, 0));
visited = vector<int>(C + 1, 0);
int a, b;
while (N--) {
cin >> a >> b;
adj[a][b] = 1;
adj[b][a] = 1;
}
dfs(1);
cout << cnt;
}예전에 풀었던 적이 있는지 실패가 떠있길래 다시 풀었다. 근데 엄청 쉽구나
여기서 고려해야할 점은 adj[i][j] 뿐만 아니라 adj[j][i] 도 간선으로 넣어줘야 한다는 점(무방향 그래프이므로!!)
이걸 하지 않았을 경우의 반례가
3
2
1 3
2 3이었다. 반례 찾기가 가장 어려워!!
10026 적록색약
#include <iostream>
#include <vector>
using namespace std;
int N, cnt = 0, rcnt = 0;
vector<vector<int>> grid;
vector<vector<int>> visit;
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, -1, 1 };
void normal(int row, int col) {
visit[row][col] = 1;
for (int i = 0; i < 4; i++) {
int nextrow = row + dy[i];
int nextcol = col + dx[i];
if (nextrow >= 0 && nextrow < N && nextcol >= 0 && nextcol < N) {
if (!visit[nextrow][nextcol] && grid[row][col] == grid[nextrow][nextcol])
normal(nextrow, nextcol);
}
}
}
void colorBlind(int row, int col) {
visit[row][col] = 1;
for (int i = 0; i < 4; i++) {
int nextrow = row + dy[i];
int nextcol = col + dx[i];
if (nextrow >= 0 && nextrow < N && nextcol >= 0 && nextcol < N) {
if (!visit[nextrow][nextcol]) {
if(grid[row][col] == grid[nextrow][nextcol] || (grid[row][col] >= 'G' && grid[nextrow][nextcol] >= 'G'))
colorBlind(nextrow, nextcol);
}
}
}
}
void dfsAll() {
visit = vector<vector<int>>(N, vector<int>(N, 0));
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (!visit[i][j]) {
normal(i, j);
++cnt;
}
}
}
visit.clear();
visit = vector<vector<int>>(N, vector<int>(N, 0));
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (!visit[i][j]) {
colorBlind(i, j);
++rcnt;
}
}
}
}
int main() {
cin >> N;
grid = vector<vector<int>>(N, vector<int>(N, 0));
char c;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> c;
grid[i][j] = c;
}
}
dfsAll();
cout << cnt << " " << rcnt;
}dy, dx 배열을 이용해서 동서남북 순회하는 방식은 자주 써야겠다! 무작정 if문으로 하려했더니 코드가 어마어마하게 길어져서 저 방식을 처음.. 써봤다.
사실 이 문제는 초반에 메모리 초과가 났다. 무작정 기존에 풀던 dfs 방식으로만 풀려고 해서..
메모리 초과 코드
#include <iostream>
#include <vector>
using namespace std;
int N, cnt = 0, rcnt = 0;
vector<vector<int>> adj;
vector<string> grid;
vector<int> visit;
void normal(int here) {
visit[here] = 1;
for (int i : adj[here]) {
if (!visit[i]) normal(i);
}
}
void colorBlind(int here) {
visit[here] = 1;
for (int i : adj[here]) {
if (!visit[i]) colorBlind(i);
}
}
void dfsAll() {
visit = vector<int>(N * N, 0);
adj = vector<vector<int>>(N * N, vector<int>(0, 0));
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (j != N - 1 && grid[i][j] == grid[i][j + 1]) {
adj[i * 5 + j].emplace_back(i * 5 + j + 1);
adj[i * 5 + j + 1].emplace_back(i * 5 + j);
}
if (i != N - 1 && grid[i][j] == grid[i + 1][j]) {
adj[i * 5 + j].emplace_back((i + 1) * 5 + j);
adj[(i + 1) * 5 + j].emplace_back(i * 5 + j);
}
}
}
for (int i = 0; i < N * N; i++) {
if (!visit[i]) {
normal(i);
++cnt;
}
}
visit.clear();
visit = vector<int>(N * N, 0);
adj.clear();
adj = vector<vector<int>>(N * N, vector<int>(N * N, 0));
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (grid[i][j] == 'G') grid[i][j] = 'R';
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (j != N - 1 && grid[i][j] == grid[i][j + 1]) {
adj[i * 5 + j].emplace_back(i * 5 + j + 1);
adj[i * 5 + j + 1].emplace_back(i * 5 + j);
}
if (i != N - 1 && grid[i][j] == grid[i + 1][j]) {
adj[i * 5 + j].emplace_back((i + 1) * 5 + j);
adj[(i + 1) * 5 + j].emplace_back(i * 5 + j);
}
}
}
for (int i = 0; i < N * N; i++) {
if (!visit[i]) {
colorBlind(i);
++rcnt;
}
}
}
int main() {
cin >> N;
for (int i = 0; i < N; i++) {
string s;
cin >> s;
grid.emplace_back(s);
}
dfsAll();
cout << cnt << " " << rcnt;
}adj 벡터를 N*N 크기로 만들어 인접 리스트를 저장하려고 했으나.. grid와 adj를 쓰고 + grid를 adj로 변환하는 과정이 두 번 있다보니 메모리 초과가 난 것 같다.
HICE 19