쌉쌀한 무화과의 개발로그

[문제]

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

[입력]

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.

둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

[출력]

각 테스트 케이스에 대해서, 섬의 개수를 출력한다.

[예제]

>문제 풀이

 기존에 4방향(상하좌우)로 뻗어나가면서 탐색했던 것에서 대각선까지 포함해주면 되는 문제

최단거리와 같은 말은 없었기 때문에 DFS로 풀었습니다.

>전체 코드

import java.util.*;

public class Main {
	static int N, M, cnt;
	static int mat[][], visited[][];
	
	public static void main(String [] args) {
		int p1, p2;
		
		Scanner scan= new Scanner(System.in);
		
		while(true) {
			cnt=0;
			M= scan.nextInt();
			N= scan.nextInt();
			if(M==0&& N==0) break;
			
			mat= new int[N][M];
			visited= new int[N][M];
			
			//입력하기
			for(int i=0; i<N; i++) {
				for(int j=0; j<M; j++) {
					mat[i][j]= scan.nextInt();
				}
			}
			
			for(int i=0; i<N; i++) {
				for(int j=0; j<M; j++) {
					if(mat[i][j]==1&&visited[i][j]!=1) { //1은 땅, 0은 바다
						cnt++;
						dfs(i, j);
					}
				}
			}
			System.out.println(cnt);
		}//while
		
	}//main
	
	public static void dfs(int x, int y) {
		int[] dx= {-1, 0, 1, 0, -1, -1, 1, 1};
		int[] dy= {0, -1, 0, 1, -1, 1, -1, 1};
		int nx, ny;
		
		visited[x][y]=1;
		
		for(int i=0; i<dx.length; i++) {
			nx= x+dx[i];
			ny= y+dy[i];
			if(nx<0||N<=nx||ny<0||M<=ny) continue;
			if(mat[nx][ny]==1&&visited[nx][ny]!=1) {
				dfs(nx, ny);
			}
		}
		
	}//end dfs
}

www.acmicpc.net/problem/4963

[문제]

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

[입력]

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

[출력]

첫째 줄에 연결 요소의 개수를 출력한다.

[예제]

>문제 풀이

 dfs로 깊이 탐색을 해주면서 한 그룹별로 cnt++를 해주면 되는 문제.

주의할 점은 간선의 연결 없이 혼자 있는 노드도 cnt++를 해줘야 한다는 점!!

(처음에 이거 처리 안해서 틀렸었다...)

bfs로 풀어도 상관 없으나, 나는 dfs로 풀었다.

>전체 코드

import java.util.*;

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

www.acmicpc.net/problem/11724

+) 단계별 풀어보기에서 어떤 알고리즘인지는 파악했으나, 구현, 응용 및 해결 능력이 부족한 것 같아서 DFS, BFS 문제를 추가로 더 풀어보려고 한다.. 그 후에는 프로그래머스 문제를 풀어볼 것이다.

[문제]

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

[입력]

입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 E(1≤E≤200,000)가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호가 빈 칸을 사이에 두고 주어진다.

[출력]

K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.

[예제]

>문제 풀이

 이분 그래프가 뭔지 찾아보다가 정답 코드를 읽어버렸다....^^;;
아마 정답코드를 보지 않았다면, 나는 인접행렬로 먼저 풀었을 것 같다.

근데 인접행렬로 풀면 메모리 초과가 난다고 한다.

이분 그래프란?

이렇게 각 포인트를 두 가지 색상으로 색칠한다고 할 때, 인접한 두 포인트(노드)의 색상이 다른 그래프를 말한다.

*풀이는 사실, 저도 겨우 이해한 것 같고 아래 블로그의 코드를 많이 참고했기 때문에...
아래 블로그를 참고하기 바랍니다.

toastfactory.tistory.com/115

>전체 코드

import java.util.*;

public class Main {
	static int K, V, E;
	static String answer;
	static ArrayList<ArrayList<Integer>> graph;
	static int[] set;
	
	public static void main(String [] args) {
		int p1, p2;
		
		Scanner scan= new Scanner(System.in);
		
		K= scan.nextInt();
		
		while(K-->0) {
			answer= "YES";
			V= scan.nextInt();
			E= scan.nextInt();
			
			graph= new ArrayList<>();
			
			for(int i=0; i<V; i++) {
				graph.add(new ArrayList<>());
			}
			
			for(int i=0; i<E; i++) {
				p1= scan.nextInt()-1;
				p2= scan.nextInt()-1;
				
				graph.get(p1).add(p2);
				graph.get(p2).add(p1);
			}
			
			set= new int[V];
			for(int i=0; i<V; i++) {
				if(set[i]==0) {
					if(!bfs(i)) break;
				}
			}
			System.out.println(answer);
		}//while
		
	}//main
	
	
	public static boolean bfs(int n) {
		Queue<Integer> queue = new LinkedList<Integer>();
		
		queue.add(n);
		set[n]= 1;
		
		while(!queue.isEmpty()) {
			n= queue.poll();
			for(Integer i: graph.get(n)) {
				if(set[n]==set[i]) {
					answer="NO";
					return false;
				}
				if(set[i]==0) {
					set[i]=set[n]*-1;
					queue.add(i);
				}
			}
		}
		return true;
	}	
}

www.acmicpc.net/problem/1707

[문제]

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

[입력]

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

[출력]

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

[예제]

>문제 풀이

 기존에 한칸 씩 이동하던 BFS문제에서 이동 거리만 조정해주면 되는 문제였습니다.

해설할게 없는,, 문제랄까,,?

>전체 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static int T, l, mat[][];
	static boolean visited[][];
	
	public static void main(String [] args) {
		int x, y, dst_x, dst_y;
		
		Scanner scan= new Scanner(System.in);
		
		T= scan.nextInt();
		while(T-->0){
			l= scan.nextInt();
			x= scan.nextInt();
			y= scan.nextInt();
			dst_x= scan.nextInt();
			dst_y= scan.nextInt();
			
			mat= new int[l][l];
			visited= new boolean[l][l];
			
			visited[x][y]=true;
			
			bfs(x, y, dst_x, dst_y);
		}
		
	}
	
	public static void bfs(int x, int y, int dst_x, int dst_y) {
		int nx, ny;
		int dx[]= {-1, -2, 1, 2, 2, 1, -2, -1};
		int dy[]= {-2, -1, -2, -1, 1, 2, 1, 2};
		
		Queue<Integer> que= new LinkedList<Integer>();
		que.offer(x);
		que.offer(y);
		
		while(!que.isEmpty()) {
			x= que.poll();
			y= que.poll();
			
			if(x==dst_x&&y==dst_y) {
				System.out.println(mat[x][y]);
				return;
			}
			for(int i=0; i<8; i++) {
				nx= x+dx[i];
				ny= y+dy[i];
				
				if(nx<0||nx>=l||ny<0||ny>=l) continue;
				
				if(mat[nx][ny]==0&&!visited[nx][ny]) {
					visited[nx][ny]=true;
					mat[nx][ny]= mat[x][y]+1;
					que.offer(nx);
					que.offer(ny);
				}
			}
			
		}//while
	}//bfs
	
}

www.acmicpc.net/problem/7562

[문제]

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다.

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

[입력]

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, 1 ≤ H ≤ 100 이다. 둘째 줄부터는 가장 밑의 상자부터 가장 위의 상자까지에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 하나의 상자에 담긴 토마토의 정보가 주어진다. 각 줄에는 상자 가로줄에 들어있는 토마토들의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0 은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다. 이러한 N개의 줄이 H번 반복하여 주어진다.

토마토가 하나 이상 있는 경우만 입력으로 주어진다.

[출력]

여러분은 토마토가 모두 익을 때까지 최소 며칠이 걸리는지를 계산해서 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

[예제]

>문제 풀이

 문제를 잘못 읽어서.. 진짜 한참을 헤맨 문제입니다....ㅎㅏ..

N x M 배열이 H번 반복되어 입력된다는 말을 똑같은 N x M 배열이 H번 쌓여져 있다고 해석해가지고..

(어쩐지..^^ 그렇게 토마토 박스 쌓을거면 2차원 배열 문제랑 뭐가 다른가 한참 생각했네요..쩝..)

문제를 제대로 해석한 후에는, mat[H][N][M] 3차원 배열과 visited[H][N][M] 3차원 배열을 이용해서 기존에 풀었던 토마토 문제(7576번)와 비슷하게 풀었습니다.

**입력

: N x M배열이 H번 반복되어 입력된다.

0: 익지 않은 토마토

1: 익은 토마토

-1: 빈 칸

*익은 토마토를 기준으로 상하좌우의 토마토들이 익어갑니다.

1.  0인 경우에 total++ 카운팅을 해줍니다.
   후에 cnt(0→1 익어간 토마토들 카운팅)와 비교해서 익지 않은 토마토가 남아있지 않은지 비교해주기 위함입니다.
2. 1인 경우 큐에 넣어줍니다. 저는 토마토의 위치정보를 Point(int h, int x, int y) 클래스에 담아서 큐에 넣었습니다.

**BFS

증감값은 dx={-1, 1, 0, 0, 0, 0}, dy={0, 0, -1, 1, 0, 0}, dh={0, 0, 0, 0, -1, 1} 배열로 선언해주었습니다.

그리고 큐.isEmpty 일 때 까지

h, x, y= q.poll();

nx=x+dx[i], ny=y+dy[i], nh= h+dh[i];

범위안에 들어오는 0≤nh≤H && 0≤nx≤N && 0≤ny≤M 에 대하여, 방문한적 없고 mat[][][]==0이면

- mat[nh][nx][ny] 방문 처리

- mat[nh][nx][ny]= mat[h][x][y]+1;

- max값 찾기 (날짜 카운팅을 위해서)

- 그리고 큐에 Point(nh, nx, ny)를 넣어주고

- cnt++; (total과 비교해서 0이었던 안익은 토마토들이 다 익었는지 비교하기 위한 변수cnt)

>전체 코드

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static int N, M, H, total, cnt=0, max=0;
	static int mat[][][];
	static boolean visited[][][];
	static Queue<Point> que;
	
	public static void main(String [] args) {
		Scanner scan= new Scanner(System.in);
		
		M= scan.nextInt();
		N= scan.nextInt();
		H= scan.nextInt();
		mat= new int[H][N][M];
		visited= new boolean[H][N][M];
		que= new LinkedList<Point>();
		
		//입력받기
		for(int i=0; i<H; i++) {
			for(int j=0; j<N; j++) {
				for(int k=0; k<M; k++) {
					mat[i][j][k]= scan.nextInt();
					if(mat[i][j][k]==1) que.offer(new Point(i,j,k));
					if(mat[i][j][k]==0) total++;
				}
			}
		}
		if(total==0) System.out.println("0");
		else bfs(0,0,0);
	}
	
	public static void bfs(int h, int x, int y) {
		int nx, ny, nh;
		Point p;
		int dh[]= {0, 0, 0, 0, -1, 1};
		int dx[]= {-1, 1, 0, 0, 0, 0};
		int dy[]= {0, 0, -1, 1, 0, 0};
		
		while(!que.isEmpty()) {
			p= que.poll();
			
			if(cnt==total) {
				System.out.println(max-1);
				return;
			}
			for(int i=0; i<6; i++) {
				nh= p.h+dh[i];
				nx= p.x+dx[i];
				ny= p.y+dy[i];
				
				if(nx<0||nx>=N||ny<0||ny>=M||nh<0||nh>=H) continue;
				
				if(mat[nh][nx][ny]==0&&!visited[nh][nx][ny]) {
					visited[nh][nx][ny]=true;
					mat[nh][nx][ny]= mat[p.h][p.x][p.y]+1;
					max=max>mat[nh][nx][ny]?max:mat[nh][nx][ny];
					que.offer(new Point(nh, nx, ny));
					cnt++;
				}
			}
			
		}//while
		System.out.println("-1");
	}//bfs
	
	static class Point {
		int x, y, h;
		
		public Point(int h, int x, int y) {
			this.h= h;
			this.x= x;
			this.y= y;
		}
	}
}

www.acmicpc.net/problem/7569