Be a developer

bfs를 통해 최소 비용을 구하는 문제다. 하루가 지나면 익는다고 했으므로, 가중치가 1이라고 할 수 있다. 토마토가 없는 곳과 마지막에 답을 출력하는 조건을 조심해야 한다. 자세한 설명은 아래 주석으로.. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 #include #include #include #include using namespace std; int n, m, ans; int ma..

dfs는 길은 찾을 수 있지만, 최소 비용을 찾을 수는 없다. bfs는 단계별로 주변으로 퍼져나가기 때문에 최소 비용문제를 풀 수 있다. 대신 가중치가 1이어야 한다. visit 배열에 거리를 계속 더해서 저장한다. 한 칸 이동하는 것을 가중치가 1 증가하는 것으로 생각한다. 따라서 visit가 0일 때만 방문하고, 0이 아닐 경우 최소 비용이 갱신되지 않으므로 방문할 필요가 없다. 코드는 아래에.. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 #include #includ..

앞에 단지번호붙이기보다 더 쉬운 문제다. 방향만 8방향으로 바뀌었을 뿐 섬과 바다만 구분하면 되기 때문에 더 쉽다. 아래는 코드.. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465#include #include #include #include #include using namespace std; int h, w;int ans;int ar[50][50];bool visit[50][50]; int dr[8] = { -1,-1,0,1,1, 1, 0,-1 };int dc[8] = { 0, 1,1,1,0,-1,-1,-1 }; void dfs(in..

그래프를 위한 vector 배열을 만들 필요가 없다. 효율적으로 풀기 위해서 visit 배열을 bool이 아니라 int 형으로 선언해서 문제에 나온 그림과 같이 번호를 넣어준다. 4방향을 check하는 것이 중요하다. sort할 때 정렬할 index를 잘 설정하자. 자세한 설명은 주석으로.. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 #include #include #include #include using namespace std; ..

1번 집합과 2번 집합으로 나눠서 생각하기 위해서, bfs, dfs에 필요한 visit 배열이나 check배열을 bool로 선언하는 것이 아니라 int 배열로 선언하여, 0은 방문하지 않은 것, 1은 1번 집합 2는 2번 집합으로 둔다. 문제에서 조건을 잘 봐야 한다. v t; while (t--) { cin >> n >> m; //테스트 케이스가 여러 개니까 check 배열을 초기화 해준다. //그래프도 초기화 해준다. for (int i = 1; i from >> to; g[from].push_back(to); g[to].push_back(from); } //방문 안한곳이 없도록 다 돌려준다. bool ok = true; for (int i = 1; i

각 정점을 돌면서 bfs를 돌리면 된다. 필요 없는 실행을 줄이기 위해서 bfs들어가기 전 방문했는지 check 배열을 통해 알아본다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include #include #include #include #include using namespace std; int n, m, ans;bool check[1000000];vector g[1001]; void bfs(int x) { queue q; //처음 넣는 node를 check해야 한다. check[x] = true; q.push(x); while (!q.empty()) { int curre..

c++로 graph를 구현하는 것은 vector의 배열을 이용하면 되므로 편하다. 그리고 queue 또한 구현되어 있어서 사용하기만 하면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 #include #include #include #include #include using namespace std; int v, e, s; bool check[10000]; vector g[10000]; void dfs(int x) ..

N과 M (2)와 같은 문제이다. 코드를 조금만 수정해주면 된다. 123456789101112131415161718192021222324252627282930313233#include #include #include #include using namespace std; int n, m;vector v; void solve(int num) { //뽑아야 할 개수만큼 뽑고 나면 출력한다. if (v.size() == m) { for (auto x : v) { printf("%d ", x); } printf("\n"); return; } for (int i = num; i > n >> m; solve(1); return 0;}Colored by Color Scriptercs