Storage Gonie

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/400 # C++(효율적이 떨어지는 방법) #include #include using namespace std; int place[101][101]; // 0 : 바다, 1: 땅 int group[101][101]; // 0 : 방문안함, 1이상 : 그룹번호 int dist[101][101]; // -1 : 방문안함, 0이상 : 방문했으며, 거리를 의미 int dx[4] = {0, -1, 0, 1}; int dy[4] = {-1, 0, 1, 0}; int main() { //데이터 입력받기 및 초기화 int n; cin >> n; for(int i = 1; i place[i][j]; group[i][j] = 0; } } //B..

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/400 # C++ #include #include using namespace std; int place[1001][1001]; // -1 : 이동할 수 없는 칸, 0 : 이동할 수 있는 칸, 1 : 이동할 수 있는 칸 int dist[1001][1001]; // -1 : 방문하지 않음, 0 이상은 방문했으며 익은 토마토 로부터의 거리를 의미 int dx[4] = {0, -1, 0, 1}; int dy[4] = {-1, 0, 1, 0}; int w, h; int main() { // 데이터 입력받기 scanf("%d %d", &w, &h); // 사용전 배열 초기화 for(int i = 1; i

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/400?category=864321 # C++ #include #include using namespace std; int miro[101][101]; // 0 : 이동할 수 없는 칸, 1 : 이동할 수 있는 칸 int dist[101][101]; // check배열의 역할 및 0 : 방문 안한 것, 1이상 : 방문한 것이면서 1,1로부터의 거리 int dx[4] = {0, -1, 0, 1}; int dy[4] = {-1, 0, 1, 0}; int h, w; int main() { scanf("%d %d", &h, &w); for(int i = 1; i

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/400 # C++(DFS) #include using namespace std; int place[51][51]; // 0 : 바다, 1 : 섬 int check[51][51]; // 0 : 방문안함, 1이상 : 섬의 번호 int dx[8] = {0, -1, -1, -1, 0, 1, 1, 1}; int dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1}; int w, h; //인접한 모든 섬을 탐색하고, 번호를 부여함 void dfs(int i, int j, int num){ check[i][j] = num; // 8개의 방향중에 갈 수 있는 경우, 그리고 방문하지 않은 경우에만 탐색 for(int k = 0; k..

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/400 # C++(DFS사용) #include #include using namespace std; int place[26][26]; // 집의 여부 표시 int check[26][26] = {}; // 0 : 방문하지 않은 것, 1이상 : 방문하였고, 부지번호 int ans[25*25] = {}; // 부지별 개수 저장 int dx[4] = {0, -1, 0, 1}; int dy[4] = {-1, 0, 1, 0}; int n; void dfs(int i, int j, int cnt) { check[i][j] = cnt; for(int k = 0; k < 4; k++){ int x = i+dx[k]; int y = j+dy[k..

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/398 # C++(재귀적 구현) #include #include using namespace std; int arr[100001]; // 인접리스트 int check[100001]; // 방문유무 및 방문순서를 저장하는 check 배열 int which_search[100001]; // 몇번째로 진행되는 탐색의 경로에 포함되는지 저장하는 배열 // 함수가 한번 호출되면 이미 방문한 정점을 찾을 때 까지 진행됨 => 이것이 가능한 이유는 모든 정점이 다음 정점을 가지기 때문에 가능함. int dfs(int node, int cnt, int &step) { // 이미 방문한 곳을 재방문하려고 한다면 이것이 사이클인지 확인해줘야 함..

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/398 # C++(비재귀 방식으로 구현) #include #include #include using namespace std; int check[300000]; // 99999일 때 9^5 * 5 = 295245 이므로 그냥 300000으로 함. // 다음 방문할 번호 구하는 함수 int get_next(int num, int p) { int next = 0; while(num != 0){ next += pow(num%10, p); num /= 10; } return next; } int main() { // check 배열 초기화 memset(check, 0, sizeof(check)); int node, p; cin >> ..

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/398 # C++(dfs탐색을 재귀 구현으로 푼것) #include #include using namespace std; int arr[1001]; // 인접 리스트 bool check[1001]; // 인접 리스트 void dfs(int node); int main() { int t; cin >> t; while(t--){ int v; cin >> v; // 정보를 입력받아 원소가 1개인 인접 리스트 생성 for (int i = 1; i > a; arr[i] = a; } // 다음 테스트 케이스를 위한 초기화 memset(check, false, sizeof(check)); // 탐색이 진행된 횟수 카운트 int ans = ..

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/398 # C++(색을 모두 칠해준 다음, 모든 간선의 양끝 정점 색을 비교함 => 비효율적) #include #include using namespace std; vector arr[20001]; // 인접 리스트 int color[20001]; // 중복방문을 막기위한 check 배열, 단 방문시 색을 저장함 void dfs(int node, int c);// DFS탐색을 진행하며 1, 2를 번갈아가며 정점에 색칠하는 함수 int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); // 테스트 케이스의 개수 입력받기 int k; cin >> k; whi..

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/398 # C++ #include #include using namespace std; vector arr[1001]; // 인접 리스트 int check[1001]; // 중복방문을 막기위한 check 배열 void dfs(int node); // DFS 탐색함수 int main() { // cin, cout 속도 빠르게 하기 ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); // 정점의 개수 n과 간선의 개수 m 입력받기 int n, m; cin >> n >> m; // 연결된 두 정점들에 대한 정보를 받아서 인접리스트 생성 for(int i = 0; i < m; i..