글 읽기 - 60%에서 틀립니다.

djgjdgjd 6년 전 0

자꾸 60%에서 틀렸다고 나오는데 어디가 왜 틀린지 모르겠습니다 ㅠ

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <queue>

using namespace std;

int T, K, N, M, l, sum = 0;
int cnt = 0;
int map[101][101];
int visit[101][101];
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};

vector<int> v;

void dfs(int x, int y)
{

    for(int i=0;i<4;i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        if(nx >= 0 && nx < M && ny >= 0 && ny < N && !visit[nx][ny] && map[nx][ny] == 0)
        {
            visit[nx][ny] = 1;
            cnt++;
            dfs(nx, ny);
        }
     
    }


}


int main()
{
    
    cin>>M>>N>>K;
    
    memset(map, 0, sizeof(map));
    memset(visit, 0, sizeof(visit));
    
  
    int x1, y1, x2, y2;
    
    for(int i=0;i<K;i++)
    {
        cin>>x1>>y1>>x2>>y2;
        for(int x=y1;x<y2;x++)
        {
            for(int y=x1;y<x2;y++)
                map[x][y] = 1;
        }
    }
    
    // 넓이에 해당하는 좌표들 1로 수정 -> 0인 부분 dfs수행
    
    
    
    for(int i=0;i<M;i++)
    {
        for(int j=0;j<N;j++)
        {
            dfs(i,j);
            
            if(cnt != 0)
                v.push_back(cnt);

            cnt = 0;
        }
    }
    
    sort(v.begin(), v.end());
    
    cout<<v.size()<<'\n';
    
    for(int i=0;i<v.size();i++)
    {
        if(i == v.size()-1)
        {
            cout<<v[i]<<'\n';
            break;
        }
        cout<<v[i]<<" ";
    }
    
    return 0;
    
}

dj910401 6년 전 1

dfs 들어가는 조건 추가와, visit을 체크해주는 부분의 위치를 바꾸었더니 정답이 나왔습니다.

아마 방문한 곳을 체크하는 것이 제대로 이루어지지 않는 것 같습니다.

dfs(i,j)에 진입 시 (i,j)를 방문을 체크하고 다음 단계로 진행되어야 하는데 이러한 부분이 문제가 아닐까 생각됩니다.

부족한 답변이라 죄송합니다. ㅠㅠ

+map배열과 visit배열을 하나로 합치면 코드가 더 간단해 질 것 같습니다.

void dfs(int x, int y)
{
    visit[x][y] = true;
    cnt++;
    for(int i=0;i<4;i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx >= 0 && nx < M && ny >= 0 && ny < N && !visit[nx][ny] && !map[nx][ny])
        {
            dfs(nx, ny);
        }
    }
}


for(int i=0;i<M;i++)
{
    for(int j=0;j<N;j++)
    {
        if(!map[i][j] && !visit[i][j])
            dfs(i,j);
            
        if(cnt != 0)
            v.push_back(cnt);
        
        cnt = 0;
    }
}

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

문제

문제

출처

ICPC

60%에서 틀립니다.

djgjdgjd 6년 전 0

dj910401 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말