글 읽기 - 안전한 영역을 찾고싶습니다..

moonsoo5522 8년 전 0

간단하게 dfs로 구현헀고

비가 아예 안올때의 예외처리도,

방문체크하는 배열의 초기화도 제대로 해줬는데 자꾸 WA가 뜹니다 ㅜㅜ..

배열 인덱스는 1,1부터 시작했습니다.

#include <stdio.h>

#define MAX(x,y) (x>y?x:y)

int mat     [102][102];
int visited [102][102];
int adj_cnt, max_cnt=1;
int wh;

void dfs(int y, int x, int cond)
{
    // 매트릭스의 범위를 벗어났거나, 이미 방문한 지역을 재방문하거나, 침수된 지역일 경우 리턴
    if(!mat[y][x] || visited[y][x] || mat[y][x]<=cond)
        return;
    
    visited[y][x]=1;
    
    dfs(y-1, x, cond);
    dfs(y, x+1, cond);
    dfs(y+1, x, cond);
    dfs(y, x-1, cond);
}
int main()
{
    scanf("%d", &wh);
    
    for(int i=1; i<=wh; i++)
        for(int j=1; j<=wh; j++)
            scanf("%d", &mat[i][j]);
    
    for(int k=0; k<=wh; k++)
    {
        // 방문하지 않은, 그리고 침수되지도 않은 지역을 순회하여 카운트를 증가시킴.
        for(int i=1; i<=wh; i++)
            for(int j=1; j<=wh; j++)
                if(!visited[i][j] && mat[i][j]>k) dfs(i, j, k), adj_cnt++;
        // 최대 카운트값 갱신
        max_cnt = MAX(max_cnt, adj_cnt);
        // 초기화 루틴
        adj_cnt=0;
        for(int i=1; i<=wh; i++)
            memset(visited[i], 0, sizeof(visited[i]));
    }
    printf("%d", max_cnt);
    return 0;
}

ntopia 8년 전 1

변수 k로 잠기는 높이 하나씩 정해보는 거 맞죠?

근데 이거 최대값을 N이라고 해놓으셨는데 땅의 높이랑 N이랑은 관련이 없어요.

입력 설명에 나와있는대로 가정하시는 게 좋을 것 같습니다.

moonsoo5522 8년 전 0

감사합니다 ㅜㅜ..

항상 조건을 건성건성 보다가 정답률이 다 깎이네요

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

문제

문제

출처

ICPC

안전한 영역을 찾고싶습니다..

moonsoo5522 8년 전 0

ntopia 8년 전 1

moonsoo5522 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말