백준 1012번 문제 질문드립니다.

Question

#include int map[52][52] = {0}, vis[52][52] = {0}, dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1}; int t, n, m, k, front = 0, rear = 0; typedef struct q { int x, y; } q; q que[52 * 52]; void push(int x, int y) { que[rear].x = x; que[rear].y = y; rear++; vis[x][y] = 1; } void pop() { front++; } void bfs(int x, int y) { int nx, ny; while (front < rear) { for (int i = 0; i < 4; i++) { nx = que[front].x + dx[i]; ny = que[front].y + dy[i]; if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue; if (map[nx][ny] != 1 || vis[nx][ny] == 1) continue; vis[nx][ny] = 1; push(nx, ny); } pop(); } } int main() { int a, b; scanf("%d", &t); while (t--) { scanf("%d %d %d", &m, &n, &k); int cnt = 0; for (int i = 0; i < k; i++) { scanf("%d %d", &a, &b); map[b][a] = 1; } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (map[i][j] == 1 && vis[i][j] == 0) { push(i, j); cnt++; bfs(i, j); } } } printf("%d ", cnt); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { vis[i][j] = 0; map[i][j] = 0; } } } return 0; }안녕하세요!!백준 bfs관련 백준 문제를 풀다 도저히 안풀려 질문드립니다.문제를 간단히 요약하자면 1과 0이 있는 2차원 배열에서 1 덩어리의 갯수를 구하는 문제입니다.https://www.acmicpc.net/problem/1012 혹시 자세한 설명을 원하시는 분들을 위해 문제 링크 남깁니다.여러 테스트케이스나 반례들을 넣었을때는 맞다고 나오는데 백준에서는 틀렸다고 나오네요.제가 틀린 부분이나 미흡한 부분 지적 및 조언 부탁드립니다.

ColoColo · Accepted Answer

재밌네요.. 백준 로그인해보니 전에 dfs로 풀어본 문제인데 덕분에 bfs로도 한번 복습하게 되는군요.일단 본문 로직은 문제 없고, 단지 각 테스트 별로 리셋해줘야 되는 변수중에 리셋이 안 된 변수들이 있어요. 코드 잘 짜셨으니 이 정도면 금방 찾으실거 같네요..

kkoko · Answer

QnA에 답변해주시는분들은 질문자님의 과외선생님이나 디버그 업무하는 직원이 아니기에 이런 질문에 무시하고 넘겨요코드 전체 복붙해서 왜안되는지 모르겠으니까 알아서 찾아서 조언까지 해주라 라는 질문은 건당 얼마씩 받으면서 답변해주는 곳 가서 하시면 됩니다이런질문 대신 헷갈리는 개념이나 지식을 코드 전문이 아닌 핵심 코드의 일부만 가져와 상세한 부연설명과 함께 질문하시면 다른 분들이 친절히 답변을 달아주실 것 같네요

백준 1012번 문제 질문드립니다.

2개의 답변

#bfs 목록