단지번호붙이기 2667

단지번호붙이기 2667

단지번호붙이기 2667

풀이코드

#include #include #include #include using namespace std; // 2667 단지번호붙이기 int n; int board[25][25]; // 인접 리스트 vector adjList[625]; bool isVisited[625]; int ret[25] = {0}; int homeCount = 0; // 상하좌우 int coord[4][2] = { {0, -1}, {-1, 0}, {1, 0}, {0, 1} }; int dfs(int currentNode){ // 출발점이 처음 들어왔을 때, 방문한 적이 있으면 0 을 return 한다. if(isVisited[currentNode]) return 0; // 현재 방문점을 방문 체크 isVisited[currentNode] = true; for(int i = 0; i < adjList[currentNode].size(); i++){ int nextNode = adjList[currentNode][i]; // 다음 노드가 방문한 적이 있으면 생략 if(isVisited[nextNode]) continue; // 없으면 homeCount++; dfs(nextNode); } return 1; } int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> n; cin.ignore(); for(int y = 0; y< n; y++){ for(int x = 0; x < n; x++){ cin >> board[y][x]; } cin.ignore(); } for(int y = 0; y < n; y++){ for(int x = 0; x < n; x++){ for(int k = 0; k < 4; k++){ int dy = y + coord[k][0]; int dx = x + coord[k][1]; // 범위를 넘으면 continue if(dy < 0 || dy >= n || dx < 0 || dx >= n) continue; // 서로 이웃한다면 if(board[y][x] == 1 || board[dy][dx] == 1){ int node1 = y * n + x; int node2 = dy * n + x; // 반복문이 돌면서, 양방향으로 넣음 adjList[node1].push_back(node2); } } } } for(int i = 0; i < n; i++){ sort(adjList[i].begin(), adjList[i].end()); } fill_n(isVisited, 1001, false); int count = 0; for(int i = 0; i < n; i++){ homeCount = 0; count += dfs(i); ret[i] = homeCount; } cout << count << '

'; for(int a : ret) cout << a << '

'; }

해설

적용한 레시피 / 방법론 + 접근법

1

풀이

1

아쉬웠던 부분 / 오답 원인 / 개선해야 할 점

1

from http://private-k.tistory.com/137 by ccl(A) rewrite - 2021-10-03 01:26:29