글 읽기 - 4963 질문합니다

xhaktmrb 3년 전 0

테스트 케이스 맞게 나오고 w,h 맞게 받고 배열 탐색할 때도 인덱스 맞게 한 것 같은데 틀리다고 나오네요 ㅜㅜ

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio> // c 문법 헤더파일
#include<string> // c++ 문자열 클래스
#include<vector> // 동적배열 라이브러리
#include<stack>
#include<queue>
#include<deque>
#include<algorithm>  // sort와 unique 사용
#include<cmath> // 제곱이나 루트함수 사용
#include<cstring> // memset 함수
#include <set>
#include <map> // map구조체
#include <numeric> //accumulate(v.begin(), v.end(), 0);

// [백준  c++ V] 
// 문제: 나이트가 한 지점으로부터 목표지점까지 이동하는데 최소이동횟수 구하기
// 접근: 최소이동횟수 -> dfs 시간초과남
// 접근2: bfs로 방문하는 배열에 이동 횟수 저장하면서 이동
// 풀이: 처음 시작하는 점에서
// 기본 bfs 하는데 이동시 이동 횟수를 저장하면서
// 8방향의 움직임을 반복문으로 구현
// 개념: memset(visited, 채우는 값, sizeof(visited)); 배열을 초기화 시킴

using namespace std; // cin,cout 편하게 사용 라이브러리
#define MAX 51

int dx[8] = { -1,-1-1,0,0,1,1,1 };
int dy[8] = { 1,0,-1,1,-1,1,0,-1 };
int visited[MAX][MAX];
int w, h;
int graph[MAX][MAX];

void dfs(int row, int col)
{
	// 8방향 검사
	for (int i = 0; i < 8; i++)
	{
		int nrow = row + dy[i];
		int ncol = col + dx[i];
		
		if (nrow >= 0 && nrow < h && ncol >= 0 && ncol < w)
		{
			if (visited[nrow][ncol] == 0 && graph[nrow][ncol] == 1)
			{
				visited[nrow][ncol] = 1;
				dfs(nrow, ncol);
				//visited[nrow][ncol] = 0; // 여기선 한번 방문한 섬은 계속 바운처리 되어야 하므로 다시 초기화 않함
			}
		}
		
	}
}

int main()
{
	// IO 속도 향상
	ios_base::sync_with_stdio(0);
	cin.tie(NULL); cout.tie(NULL);// 입출력 시간 단축
	
	// 입력
	while (1)
	{
		cin >> w >> h;
		if (w == 0 && h == 0) { return 0; }
		for (int i = 0; i < h; i++)
		{
			for (int j = 0; j < w; j++)
			{
				cin >> graph[i][j];
			}
		}
		int cnt = 0;
		// 완전탐색 dfs
		for (int i = 0; i < h; i++)
		{
			for (int j = 0; j < w; j++)
			{
				if (visited[i][j] == 0 && graph[i][j] == 1)
				{
					visited[i][j] = 1;
					dfs(i, j);
					cnt++;
				}
				
			}
		}
		// 방문배열 초기화
		memset(visited, 0, sizeof(visited));
		memset(graph, 0, sizeof(graph));
		cout << cnt << '\n';
	}
	
	
	return 0;
}

djm03178 3년 전 0

28번째 줄의 -1-1을 -1,-1로 바꾸어주면 맞습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

4963 질문합니다

xhaktmrb 3년 전 0

djm03178 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말