글 읽기 - 반례를 못찾겠습니다. ㅠㅠ

ashi3914 5년 전 1

예시입력값을 넣었을떄는 잘 나오더군요 문제는 제출했을때 오답으로 뜨네요 ㅠㅠ

알고리즘에 문제가 있는걸까요?? 있다면 어디에 있는지 도와주시면 감사하겠습니다 ㅠ

import java.util.*;
import java.util.StringTokenizer;
import java.io.*;
import java.math.BigInteger;
import java.math.*;
import java.util.Queue;



public class practice {

	static int n,ans;
	static int map[][];
	static int dx[]={-1,1,0,0};
	static int dy[]={0,0,-1,1};
	static int visited[][];
	
	public static int dfs(int y,int x){
		
		
		int result=1;
		visited[y][x]=1;
		
		for(int i=0;i<4;i++){
			
			int ny=y+dy[i];
			int nx=x+dx[i];
			
			if(ny>=0 && nx>=0 && ny<n && nx<n && visited[ny][nx]==0){
				if(map[ny][nx]==1){
					
					result+=dfs(ny,nx);
					
				}
			}
		}
		
		return result;
	}

	public static void main(String args[]){

		Scanner sc=new Scanner(System.in);

		int cnt=0;
		
		n=sc.nextInt();
		int sum[]=new int[100001];
		map=new int[n][n];
		visited=new int[n][n];
		String input[]=new String[n];
		for(int i=0;i<n;i++){
			input[i]=sc.next();
			for(int j=0;j<n;j++){
				map[i][j]=input[i].charAt(j)-'0';
			}
		}
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				if(visited[i][j]==0 && map[i][j]==1){
					
					cnt++;//단지 개수
					sum[cnt]=dfs(i,j);
				}
			}
		}
		System.out.println(cnt);
		for(int i=1;i<=cnt;i++){
			System.out.println(sum[i]);
		}
	}
}

kimsy96 5년 전 0

이곳에 답이 있을지도..

https://www.acmicpc.net/board/...

ashi3914 5년 전 0

감사합니다. 덕분에 해결했습니다.

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

문제

문제

출처

ICPC

반례를 못찾겠습니다. ㅠㅠ

ashi3914 5년 전 1

kimsy96 5년 전 0

ashi3914 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말