쌉쌀한 무화과의 개발로그

[문제]

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

[입력]

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

[출력]

첫 번째 줄에는 총 단지수를 출력하시오.

그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

[예제]

>문제 풀이

 dfs 코드가 더 간단한 것 같아서 dfs로 풀었습니다. 아직 bfs는 로직이 눈에 잘 안익네요..ㅎㅎ

int N     //지도의 크기

int cnt   //연결된 집의 개수를 체크하기 위한 변수

int mat[][]      //입력 배열

int visited[][]   //방문 여부 체크

입력값은 띄어쓰기가 안된채로 들어오기 때문에 String으로 받은 후에 Integer.parseInt(charAt()) 으로 캐스팅하여 mat[][]배열에 넣어주었습니다.

그리고 mat[][]==1이고 visited!=1인 i와 j를 dfs로 넘겨서 상하좌우에 연결된 집들을 체크했습니다.

dfs(x, y)

들어온 x와 y에 대하여 visited[x][y]=1로 바꿔주고(1이면 방문했다는 뜻), cnt++; 카운팅을 해줍니다.

그리고 상하 좌우 값들인 0≤(x-1, y), (x, y-1), (x+1, y), (x, y+1)<N 을 체크하여 dfs로 recursion 해줍니다.

>전체 코드

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	static int N, cnt=0;
	static int visited[][], mat[][];
	
	public static void main(String [] args) {
		String str;
		ArrayList<Integer> answer= new ArrayList<>(); //정답을 담을 리스트
		
		Scanner scan= new Scanner(System.in);
		
		N= scan.nextInt();
		visited= new int[N][N];
		mat= new int[N][N];
		
		for(int i=0; i<N; i++) {  //문자열로 입력받고 char 하나씩 배열로
			str= scan.next();
			for(int j=0; j<N; j++) {
				mat[i][j]= Integer.parseInt(str.charAt(j)+"");
			}
		}
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(mat[i][j]==1&&visited[i][j]!=1) { //matrix 값이 1인데, 방문한적 없으면
					cnt=0;
					dfs(i, j);
					answer.add(cnt);
				}
			}
		}//end
		
		System.out.println(answer.size());
		answer.sort(null);
		for(int i=0; i<answer.size(); i++) {
			System.out.println(answer.get(i));
		}
	}
	
	static int[] dx= {-1, 0, 0, 1}; //x값에 대한 증감
	static int[] dy= {0, -1, 1, 0}; //y값에 대한 증감
	public static void dfs(int x, int y) {
		int nowx, nowy;
		visited[x][y]=1;
		cnt++;
		
		for(int i=0; i<4; i++) { //상하좌우의 값들을 확인하기 위해
			nowx= x+dx[i];
			nowy= y+dy[i];
			if(nowx>=0&&nowx<N&&nowy>=0&&nowy<N) { //0<=nowx<N && 0<=nowy<N
				if(mat[nowx][nowy]==1&&visited[nowx][nowy]!=1) {
					dfs(nowx, nowy);
				}
			}
		}
	}//dfs
	
}

www.acmicpc.net/problem/2667

[문제]

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

[입력]

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

[출력]

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

[예제]

>문제 풀이

 문제의 이해도, 풀이도 어렵지 않은 문제

dfs와 bfs 둘 중 하나를 이용해서, 노드에 방문할 때마다 카운팅 해주면 되는 문제입니다.

(단, 1이 감염시킨 컴퓨터를 찾아야해서 1번 컴퓨터는 카운팅에서 빼주어야합니다.)

>전체 코드

import java.util.Scanner;

public class Main {
	static int N, M, cnt=0;
	static int visit[], mat[][];
	
	public static void main(String [] args) {
		int p1, p2;
		
		Scanner scan= new Scanner(System.in);
		
		N= scan.nextInt();
		M= scan.nextInt();
		
		visit= new int[N+1];
		mat= new int[N+1][N+1];
		for(int i=0; i<M; i++) {
			p1= scan.nextInt();
			p2= scan.nextInt();
			mat[p1][p2]=mat[p2][p1]=1;
		}
		
		dfs(1);
		System.out.println(cnt-1);
	}
	
	public static void dfs(int start) {
		visit[start]=1;
		cnt++;
		for(int i=1; i<=N; i++) {
			if(mat[start][i]==1 && visit[i]!=1) {
				dfs(i);
			}
		}
	}//dfs
	
}

www.acmicpc.net/problem/2606

[문제]

양팔 저울과 몇 개의 추가 주어졌을 때, 이를 이용하여 입력으로 주어진 구슬의 무게를 확인할 수 있는지를 결정하려고 한다.

무게가 각각 1g과 4g인 두 개의 추가 있을 경우, 주어진 구슬과 1g 추 하나를 양팔 저울의 양쪽에 각각 올려놓아 수평을 이루면 구슬의 무게는 1g이다. 또 다른 구슬이 4g인지를 확인하려면 1g 추 대신 4g 추를 올려놓으면 된다.

구슬이 3g인 경우 아래 <그림 1>과 같이 구슬과 추를 올려놓으면 양팔 저울이 수평을 이루게 된다. 따라서 각각 1g과 4g인 추가 하나씩 있을 경우 주어진 구슬이 3g인지도 확인해 볼 수 있다.

<그림 2>와 같은 방법을 사용하면 구슬이 5g인지도 확인할 수 있다. 구슬이 2g이면 주어진 추를 가지고는 확인할 수 없다.

추들의 무게와 확인할 구슬들의 무게가 입력되었을 때, 주어진 추만을 사용하여 구슬의 무게를 확인 할 수 있는지를 결정하는 프로그램을 작성하시오.

[입력]

첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무게는 500g이하이며, 입력되는 무게들 사이에는 빈칸이 하나씩 있 다. 세 번째 줄에는 무게를 확인하고자 하는 구슬들의 개수가 주어진다. 확인할 구슬의 개수는 7이하이다. 네 번째 줄에는 확인하고자 하는 구슬들의 무게가 자연수로 주어지며, 입력되는 무게들 사이에는 빈 칸이 하나씩 있다. 확인하고자 하는 구슬의 무게는 40,000보다 작거나 같은 자연수이다.

[출력]

주어진 각 구슬의 무게에 대하여 확인이 가능하면 Y, 아니면 N 을 차례로 출력한다. 출력은 한 개의 줄로 이루어지며, 각 구슬에 대한 답 사이에는 빈칸을 하나씩 둔다.

[예제]

>문제 풀이

간단히 문제를 요약하자면, N개의 추가 주어지고, M개의 질문들이 주어진다.

boolean dp 배열에 N개의 추를 조합하여 만들 수 있는 값들은 dp[값]=true로 설정해준다.

질문에 따라 dp배열 값이 true면 Y를, false이면 N을 출력해주면 된다.

dp의 메모이제이션과 dfs를 모두 써서 풀었다. (for문으로만 풀 수도 있지만, 나는 dfs를 썼다.)

bottom-up으로 arr[i] 값을 더했을 때, 더하지 않았을 때, 빼주었을 때를 각각 재귀로 돌렸다.

(무슨 말인지는 코드를 보면 더 이해하기 쉬울 것이다.)

	public static void find_dp(int idx, int weight) {
		if(dp[idx][weight]) return;
		dp[idx][weight]=true;
		if(idx==N) return;
		
		find_dp(idx+1, weight+arr[idx+1]);
		find_dp(idx+1, weight);
		find_dp(idx+1, Math.abs(weight-arr[idx+1]));
	}

이 부분이 이 문제를 풀기위한 핵심 아이디어? 코드 부분이다.

*이 문제를 풀 때 주의할 점이 몇가지 있는데,

• 추의 개수 30개, 추 1개의 최대무게는 500g >>즉, 15000이 만들 수 있는 무게의 최대값이다.
  그러나, 질문할 수 있는 무게값의 최대는 40000이다.
  질문을 받고 dp[질문한 무게]값이 true인지 아닌지 확인할 때 ArrayIndexOutOfBoundsException이 발생할 수 있다.
• 또한 문제의 입력을 받는데 Scanner를 사용, 출력할 때 System.out.print()를 사용하게 되면 시간초과가 발생한다.나는 입력에서는 BufferedReader와 StringTokenizer 그리고 출력에서는 StringBuilder를 사용했다.

>전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
	static int N, M, question, max=15000, arr[];
	static boolean dp[][];
	
	public static void main(String [] args) throws IOException {
		
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		
		N= Integer.parseInt(br.readLine());
		arr= new int[N+1];
		dp= new boolean[31][max+1];
		
		StringTokenizer st= new StringTokenizer(br.readLine());
		for(int i=1; i<=N; i++) {
			arr[i]= Integer.parseInt(st.nextToken());
		}
		
		find_dp(0,0);
		
		StringBuilder sb= new StringBuilder();
		M= Integer.parseInt(br.readLine());
		st= new StringTokenizer(br.readLine());
		for(int i=0; i<M; i++) {
			question= Integer.parseInt(st.nextToken());
			if(question>15000)  sb.append("N ");
			else sb.append(dp[N][question]?"Y ":"N ");
		}
		System.out.println(sb);
		br.close();
	}
	
	public static void find_dp(int idx, int weight) {
		if(dp[idx][weight]) return;
		dp[idx][weight]=true;
		if(idx==N) return;
		
		find_dp(idx+1, weight+arr[idx+1]);
		find_dp(idx+1, weight);
		find_dp(idx+1, Math.abs(weight-arr[idx+1]));
	}
}

문제출처: https://www.acmicpc.net/problem/2629