문제풀이

이 문제는 이전에 풀었던 토마토 문제의 업그레이드 버전이다

원래 2차원 배열 탐색으로 주어졌던 저번이랑 달리 3차원 배열을 탐색해야 한다.

따라서 방향 벡터가 4개 -> 6개로 추가되는 점 주의해서 저번이랑 똑같이 코딩하면 된다.

2021.10.26 - [Programming/Algorithm] - [BFS] BOJ 7576번, 토마토 (JAVA)

위 글을 참고하시길 바랍니다.

소스코드

https://www.acmicpc.net/problem/7569

문제풀이

다른 BFS 문제와 비슷하게 R, G, B가 각각 연속적으로 이어진 영역의 개수를 구해주면된다.

적록색약인 사람은 R과 G가 똑같이 보이므로 BFS를 돌리기전에 배열의 R => G 로 변경해주었다.

이 방법 말고도 BFS안에서 현재 색이 R이거나 G일때를 확인해서 돌려도 괜찮을것같다.

소스코드

https://www.acmicpc.net/problem/10026

문제풀이

1. 알파벳이 나왔는지 확인할 수 있는 배열을 만들어서 해당 문자를 아직 방문하지 않았을 경우에만 방문하는

방법을 사용한다.

2. dfs 매개변수로 현재까지 나온 문자열을 전달하여 이 문자열에 포함되어 있지않으면 다음 문자를 추가해 주는 방식

이때 s.contains(Chracter.toString(arr[ny][nx]))  이러한 방법을 이용하는데 이 contains 라는 메소드가 배열 길이 만큼 시간이 걸린다. 이걸 dfs로 돌리면 시간이 매우 오래 걸리지만 통과는 하는 듯 싶다.

두가지 방법을 모두 한번씩 확인해보고 왜 1번 방법이 더 빠른지 생각해보면 좋을듯 싶다.

소스코드1

소스코드2

문제풀이

- 이 문제는 플로이드 와샬(Floyd Warshall) 알고리즘 문제이다.

플로이드 와샬 알고리즘은 모든 정점에서 모든 정점으로의 거리의 최소값을 구할 수 있다.

a 정점에서 b 정점으로 이동 하는 배열을 입력받아서

a -> k -> b 로 가는 경로가 존재하는지 확인하며 값을 채워 넣는다.

시간 복잡도는 O(n^3) 이 걸리는 방법이다.

https://www.youtube.com/watch?v=9574GHxCbKc 

이 영상을 참고하여 공부하였다.

대학때 알고리즘 수업을 들었었는데, 대학수업 보다 요즘 코딩 유튜버들이 훨씬 설명을 잘한다고 느낀다.

소스코드

안전 영역

문제

재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다.

어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어지며 배열의 각 원소는 해당 지점의 높이를 표시하는 자연수이다. 예를 들어, 다음은 N=5인 지역의 높이 정보이다.

6	8	2	6	2
3	2	3	4	6
6	7	3	3	2
7	2	5	3	6
8	9	5	2	7

이제 위와 같은 지역에 많은 비가 내려서 높이가 4 이하인 모든 지점이 물에 잠겼다고 하자. 이 경우에 물에 잠기는 지점을 회색으로 표시하면 다음과 같다. 

6	8	2	6	2
3	2	3	4	6
6	7	3	3	2
7	2	5	3	6
8	9	5	2	7

물에 잠기지 않는 안전한 영역이라 함은 물에 잠기지 않는 지점들이 위, 아래, 오른쪽 혹은 왼쪽으로 인접해 있으며 그 크기가 최대인 영역을 말한다. 위의 경우에서 물에 잠기지 않는 안전한 영역은 5개가 된다(꼭짓점으로만 붙어 있는 두 지점은 인접하지 않는다고 취급한다). 

또한 위와 같은 지역에서 높이가 6이하인 지점을 모두 잠기게 만드는 많은 비가 내리면 물에 잠기지 않는 안전한 영역은 아래 그림에서와 같이 네 개가 됨을 확인할 수 있다. 

6	8	2	6	2
3	2	3	4	6
6	7	3	3	2
7	2	5	3	6
8	9	5	2	7

이와 같이 장마철에 내리는 비의 양에 따라서 물에 잠기지 않는 안전한 영역의 개수는 다르게 된다. 위의 예와 같은 지역에서 내리는 비의 양에 따른 모든 경우를 다 조사해 보면 물에 잠기지 않는 안전한 영역의 개수 중에서 최대인 경우는 5임을 알 수 있다. 

어떤 지역의 높이 정보가 주어졌을 때, 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 계산하는 프로그램을 작성하시오. 

입력

첫째 줄에는 어떤 지역을 나타내는 2차원 배열의 행과 열의 개수를 나타내는 수 N이 입력된다. N은 2 이상 100 이하의 정수이다. 둘째 줄부터 N개의 각 줄에는 2차원 배열의 첫 번째 행부터 N번째 행까지 순서대로 한 행씩 높이 정보가 입력된다. 각 줄에는 각 행의 첫 번째 열부터 N번째 열까지 N개의 높이 정보를 나타내는 자연수가 빈 칸을 사이에 두고 입력된다. 높이는 1이상 100 이하의 정수이다.

출력

첫째 줄에 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 출력한다.

문제풀이

1. 물에 높이에 따라 BFS의 탐색 범위가 변경될때 안전 영역의 개수를 구하는 문제.

// 틀린 방법

물의 높이는 1부터 시작해서 [최대 건물 높이 -1] 만큼 반복작업

[건물 높이] > [물 높이] 

이때 건물높이가 1 일때 문제 발생

//맞는 방법

물의 높이를 0부터 시작하여 BFS를 구하였더니 정답이 나왔다.

**

내가 잘못 생각한건가? 장마가 온다고했으니 적어도 1일때 부터 탐색을 시작해야 한다고 생각하는데

혹시 이 글을 읽으시는 분은 어떻게 생각하는지 답글 부탁드립니다.

소스코드

섬의 개수

문제

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

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

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

입력

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

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

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

출력

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

문제풀이

이 문제는 지금까지 풀었던 문제들과는 다르게 대각선에 있는 (y,x)의 좌표에서 대각선의 위치도 이동이 가능하다.

따라서 기존 상하좌우만 탐색했을경우

방향백터를 

static int[] dx = {1, -1, 0, 0};
static int[] dy = {0, 0, -1, 1};

위 와 같이 사용하였는데

static int[] dx = {1, -1, 0, 0, 1, 1, -1, -1};
static int[] dy = {0, 0, -1, 1, 1, -1, 1, -1};

대각선의 위치도 고려하기 위해서 다음과 같이 변경해주었다.

소스코드

import java.util.*;
import java.io.*;
class Main{
	static int n, m;
	static int[][] map;
	static boolean[][] visited;
	static int[] dx = {1, -1, 0, 0, 1, 1, -1, -1};
	static int[] dy = {0, 0, -1, 1, 1, -1, 1, -1};
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		while(true)
		{
			//INPUT		
			StringTokenizer st = new StringTokenizer(br.readLine());
			m = Integer.parseInt(st.nextToken());
			n = Integer.parseInt(st.nextToken());
			
			if(m==0 && n==0) break;
			
			map = new int[n][m];
			visited = new boolean[n][m];
			int cnt = 0;
			for(int i=0;i<n;i++)
			{
				st = new StringTokenizer(br.readLine());
				for(int j=0;j<m;j++)
				{
					map[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
			for(int i=0;i<n;i++)
			{
				for(int j=0;j<m;j++)
				{
					if(!visited[i][j] && map[i][j] == 1)
					{
						bfs(i,j);
						cnt++;
					}
				}
			}
			sb.append(cnt).append('\n');
		}
		System.out.println(sb);
	}	
	
	static void bfs(int y, int x)
	{
		Queue<Pos> q = new LinkedList<>();
		q.add(new Pos(y,x));
		visited[y][x] = true;
		
		while(!q.isEmpty())
		{
			Pos p = q.poll();
			for(int i=0;i<8;i++)
			{
				int ny = p.y + dy[i];
				int nx = p.x + dx[i];
				if(ny >=0 && nx >=0 && ny <n && nx < m)
				{
					if(!visited[ny][nx] && map[ny][nx] == 1)
					{
						visited[ny][nx] = true;
						q.add(new Pos(ny,nx));
					}
				}
			}
		}
	}
}
class Pos{
	int y, x;
	public Pos(int y, int x)
	{
		this.y = y;
		this.x = x;
	}
}

최단경로

문제

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

입력

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

출력

첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

문제풀이

문제와 같이 한 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘으로 다익스트라 알고리즘이 있다.

https://www.youtube.com/watch?v=611B-9zk2o4&t=950s 

dist 배열의 값을 갱신 해나가면서 한 정점에서 모든 정점까지의 최단경로를 구할 수 있다.

위의 영상을 참고하면서 자신의 스타일에 맞게 코딩하는것에 익숙해지면 좋다.

같은 알고리즘이라도 사람마다 스타일이 다르기 때문에 좀 더 편한 방법이 있다.

비슷한 유형을 계속해서 풀어보면서 자신만의 방법을 찾는것이 중요하다고 생각한다.

비슷한 유형의 다른 문제로는

https://programmers.co.kr/learn/courses/30/lessons/12978

프로그래머스의 배달이라는 문제가 있다.

이 문제에서는 주어진 K 보다 작은 거리에 있는 지점의 개수를 출력하는 문제이다.

나 같은 경우는 PriorityQueue를 사용해서 거리가 작은 순으로 정렬된 값을 이용하는 방법을 사용한다.

소스코드

import java.util.*;
import java.io.*;
class Main{
	static int n, m, start;
	static List<Node>[] nodes;
	static int[] dist;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		//INPUT		
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		start = Integer.parseInt(br.readLine());
		nodes = new ArrayList[n+1];
		dist = new int[n+1];
		for(int i=1;i<=n;i++)
		{
			nodes[i] = new ArrayList<>();
			dist[i] = Integer.MAX_VALUE;
		}
		for(int i=0;i<m;i++)
		{
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			//a -> b로 연결되어 있고 비용은 c 이다.
			nodes[a].add(new Node(b,c));
		}
		
		dijkstra(start);
		
		for(int i=1;i<=n;i++)
		{
			if(dist[i] == Integer.MAX_VALUE)
				sb.append("INF").append('\n');
			else
				sb.append(dist[i]).append('\n');
		}
		System.out.println(sb);
	}	
	
	static void dijkstra(int start)
	{
		//연결된 노드에서 거리가 작은 순으로 탐색하기 위해 PriorityQueue를 이용
		PriorityQueue<Node> pq = new PriorityQueue<>(new Comparator<Node>(){
			public int compare(Node a, Node b)
			{
				if(a.dist < b.dist) return -1;
				else if(a.dist > b.dist) return 1;
				else return 0;
			}
		});
		//시작위치는 거리가 0
		pq.add(new Node(start,0));
		dist[start] = 0;
		while(!pq.isEmpty())
		{
			Node n = pq.poll();
			int now = n.node;
			int cost = n.dist;
			for(int i=0;i<nodes[now].size();i++)
			{
				int next = nodes[now].get(i).node;
				int nCost = nodes[now].get(i).dist;
				//지금까지 탐색한 거리보다
				//현재위치에서 next를 가는데 비용이 더 적게 들면 갱신
				if(dist[next] > cost + nCost)
				{
					dist[next] = cost+nCost;
					pq.add(new Node(next, dist[next]));
				}
			}
		}
	}
}

class Node{
	int node;
	int dist;
	public Node(int a, int b)
	{
		node = a;
		dist = b;
	}
}

연구소

문제

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.

연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 

일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.

예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자.

2 0 0 0 1 1 0 0 0 1 0 1 2 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0

이때, 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다. 아무런 벽을 세우지 않는다면, 바이러스는 모든 빈 칸으로 퍼져나갈 수 있다.

2행 1열, 1행 2열, 4행 6열에 벽을 세운다면 지도의 모양은 아래와 같아지게 된다.

2 1 0 0 1 1 0 1 0 1 0 1 2 0 0 1 1 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0

바이러스가 퍼진 뒤의 모습은 아래와 같아진다.

2 1 0 0 1 1 2 1 0 1 0 1 2 2 0 1 1 0 1 2 2 0 1 0 0 0 1 2 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0

벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 위의 지도에서 안전 영역의 크기는 27이다.

연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.

빈 칸의 개수는 3개 이상이다.

출력

첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.

문제풀이

1. 이차원 배열에서 0인 위치( 빈칸 ) 세 곳을 벽(1)로 만든다.

2. 해당 배열을 복사한 후 복사한 배열에서 바이러스를 퍼지게 한 후 남은 빈칸의 개수의 최대값을 구한다.

우선 빈칸 3개의 경우 모두를 뽑을 수 있어야 한다.

이러한 경우 조합 알고리즘을 이용한다.

2021.09.24 - [Programming/Algorithm] - 순열과 조합

다음 순열과 조합 관련 게시물을 참고하여 Combination 방법에 대해서 참고하자.

세개의 벽을 골랐으면 이제 바이러스를 퍼뜨릴 차례이다.

이때에는 BFS, DFS 원하는 방법을 사용하면 된다.

나 같은 경우는 BFS가 좀 더 직관적으로 이해하기 편해서 BFS를 이용하였다.

바이러스와 인접한 위치에 0(빈칸)이 있으면 바이러스로 바꿔주고 해당위치를 Queue에 넣어 반복 작업을 한다.

소스코드

import java.util.*;
import java.io.*;
class Main{
	static int n, m;
	static int[][] map;
	static boolean[][] visited;
	static boolean[] selected;
	static int[] dx = {1, -1, 0, 0};
	static int[] dy = {0, 0, 1, -1};
	static List<Pos> empty = new ArrayList<>();
	static int max;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		map = new int[n][m];
		selected = new boolean[n*m];
		for(int i=0;i<n;i++)
		{
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<m;j++)
			{
				map[i][j] = Integer.parseInt(st.nextToken());
				if(map[i][j] == 0)
					empty.add(new Pos(i,j));
			}
		}
		dfs(0,0);
		
		System.out.println(max);
		
	}
	
	//조합
	static void dfs(int depth, int idx)
	{
		if(depth == 3)
		{
			int[][] copy_map = new int[n][m];
			for(int i=0;i<n;i++)
			{
				for(int j=0;j<m;j++)
				{
					copy_map[i][j] = map[i][j];
				}
			}
			int cnt = 0;
			for(int i=0;i<empty.size();i++)
			{
				if(cnt == 3) break;
				if(selected[i])
				{
					copy_map[empty.get(i).y][empty.get(i).x] = 1;
					cnt++;
				}
			}
			int sum = virus(copy_map);
			max = Math.max(sum, max);
			return;
		}
		for(int i=idx;i<empty.size();i++)
		{
			if(selected[i])continue;
			selected[i] = true;
			dfs(depth+1, i);
			selected[i] = false;
		}
	}
	static int virus(int[][] map2)
	{
		Queue<Pos> q = new LinkedList<>();
		visited = new boolean[n][m];
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<m;j++)
			{
				if(map2[i][j] == 2)
				{
					q.add(new Pos(i,j));
					visited[i][j] = true;
				}
			}
		}
		
		//바이러스(2) 와 인접한 칸이 빈칸일 경우
		//바이러스 퍼뜨리기.
		while(!q.isEmpty())
		{
			Pos now = q.poll();
			for(int i=0;i<4;i++)
			{
				int ny = now.y + dy[i];
				int nx = now.x + dx[i];
				if(ny >=0 && nx >=0 && ny <n && nx < m)
				{
					if(!visited[ny][nx] && map2[ny][nx] == 0)
					{
						q.add(new Pos(ny,nx));
						visited[ny][nx] = true;
						map2[ny][nx] = 2;
					}
				}
			}
		}
		
		//바이러스를 퍼뜨리고 난 후
		//0 의 개수 카운딩
		int empty = 0;
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<m;j++)
			{
				if(map2[i][j] == 0)
					empty++;
			}
		}
		return empty;
	}
}
class Pos{
	int y,x;
	public Pos(int y, int x)
	{
		this.y = y;
		this.x = x;
	}
}