4963번 - 섬의 개수
2667번 보다 조금 더 쉬운 난이도의 문제였다.
단지 생각할 점은 대각선의 섬까지 걸어갈 수 있는 것으로 생각하기 때문에 dx,dy 를 대각선까지 포함시켜야 했다.
또한 습관적으로 입력값에 대해서 생각을 안했었는데
w,h 로 들어오는 값은 내가 코딩하는 방식과 반대여서 x값으로 h , y값으로 w를 써야했는데 간과했었다.
<정답 코드 - BFS , DFS (사용할 함수만 주석을 제거)>
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 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 | #include<iostream> #include<string.h> #include<queue> using namespace std; int dx[8] = { -1,-1,0,1,1,1,0,-1 }; int dy[8] = { 0,1,1,1,0,-1,-1,-1 }; int map[51][51]; bool check[51][51]; int cnt; int w, h; void bfs(int x,int y) { queue<pair<int, int>> q; q.push(make_pair(x, y)); check[x][y] = true; while (!q.empty()) { int now_x = q.front().first; int now_y = q.front().second; q.pop(); for (int d = 0; d < 8; d++) { int next_x = now_x + dx[d]; int next_y = now_y + dy[d]; if (next_x >= 0 && next_y >= 0 && next_x < h && next_y < w && map[next_x][next_y] == 1 && !check[next_x][next_y]) { check[next_x][next_y] = true; q.push(make_pair(next_x, next_y)); } } } } void dfs(int now_x, int now_y) { check[now_x][now_y] = true; for (int d = 0; d < 8; d++) { int next_x = now_x + dx[d]; int next_y = now_y + dy[d]; if (next_x >= 0 && next_y >= 0 && next_x < h && next_y < w && map[next_x][next_y] == 1 && !check[next_x][next_y]) { check[next_x][next_y] = true; dfs(next_x, next_y); } } } int main() { while ((cin >> w >> h)&&(w!=0 && h!=0)) { cnt = 0; memset(map, 0, sizeof(map)); memset(check, false, sizeof(check)); for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { cin >> map[i][j]; } } for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { if (map[i][j] == 1 && !check[i][j]) { cnt++; //bfs(i, j); //dfs(i, j); } } } cout << cnt << endl; } return 0; } | cs |
반응형