개발생각

[Baekjoon][https://www.acmicpc.net/problem/2178]

지나야 하는 최소 칸 수를 구하는 문제로 -> 너비 우선 탐색(BFS) 알고리즘

미로에서 1은 이동이 가능한 구역으로, 첫 시작 위치 좌표 값(map[0][0])을 Queue에 넣고 BFS 알고리즘을 적용한다.

Queue에 값이 존재 하지 않을 때까지 상, 하, 좌, 우로 이동 가능한 인접한 지역(map[n][m] == 1) &&

방문하지 않은 미로 (visit[n][m] ==0)에 방문하여 해당 좌표 값을 Queue에 추가한다.

지나온 미로 칸 수는 상, 하, 좌, 우 이동이 모두 완료된 시점마다 지나온 칸수를 +1씩 추가해준다.

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

class Location2178{
	
	int x;
	int y;
	
	public Location2178(int x, int y) {
		// TODO Auto-generated constructor stub
		this.x = x;
		this.y = y;
	}
}

public class Main {

	static int n;
	static int m;
	static int[][] map;
	static int[][] visit;
	static Queue<Location2178> q;
	static int movement_cnt = 0;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		m = sc.nextInt();
		q = new LinkedList<>();
		map = new int[n][m];
		visit = new int[n][m];
		
		for(int i=0;i<n;i++){
			String str = sc.next();
			for(int j=0;j<m;j++) {
				map[i][j] = (int)str.charAt(j) - 48;
				if(i==0 && j==0 && map[i][j] == 1) {
					q.offer(new Location2178(i, j));
					visit[i][j] = 1;
				}
			}
		}
				
		getBFS();
		
		System.out.println(movement_cnt+1);
	}
	
	public static void getBFS() {
		int[] xx = {-1, 0, 1, 0};
		int[] yy = {0, 1, 0, -1};
		
		while(!q.isEmpty()) {			
			
			int location_size = q.size();
			for(int j=0;j<location_size;j++) {
				int x = q.peek().x;
				int y = q.poll().y;
				
				if(x==n-1 && y== m-1) {
					return;
				}
				
				for(int i=0;i<4;i++) {
					int ax = x+xx[i];
					int ay = y+yy[i];
					
					if(ax >=0 && ax<n && ay>=0 && ay<m) {
						if(map[ax][ay] == 1 && visit[ax][ay] == 0)
						{
							q.offer(new Location2178(ax, ay));
							visit[ax][ay] = 1;
						}
					}
				}
			}
			
			movement_cnt++;
		}
	}
}

[Baekjoon][https://www.acmicpc.net/problem/7576]

- 너비 우선 탐색(BFS) 알고리즘

정수 1은 익은 토마토로 하루가 지나면 상, 하, 좌, 우로 인접한 익지 않은 토마토에게 영향을 준다. 출력해야할 답은 보관된 토마토들이 몇일이 지나면 다 익게 되는지 최소 일수를 구하는 문제로 너비 우선 탐색(BFS) 알고리즘을 적용했다.

창고 Map[n][m] 을 입력하면서 Queue에 현재 익은 토마토의 위치를 저장 후 BFS 알고리즘을 호출한다.

Queue에 값이 존재 하지 않을 때까지 인접한 익지 않은 토마토(map[n][m] ==0) && 방문하지 않은 좌표(visit[n][m] == 0) 에 방문하여 익지 않은 토마토를 익은 토마토로 값을 변경하여 저장.

이후 Queue에 더 이상 값이 존재 하지 않을 때의 날짜를 출력한다.

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

class TomatoLocation{
	int x;
	int y;
	
	public TomatoLocation(int x, int y) {
		// TODO Auto-generated constructor stub
		this.x = x;
		this.y = y;
	}
}

public class Main {

	static int m;
	static int n;
	static int[][] map;
	static int[][] visit;
	static Queue<TomatoLocation> t;
	static int result_cnt = -1;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner sc = new Scanner(System.in);
		
		m = sc.nextInt(); // 가로
		n = sc.nextInt(); // 높이
		
		map = new int[n][m];
		visit = new int[n][m];
		t = new LinkedList<TomatoLocation>();
		
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<m;j++)
			{
				map[i][j] = sc.nextInt();
				if(map[i][j] == 1 && visit[i][j] == 0) {
					t.offer(new TomatoLocation(i, j));
				}
			}
		}
		
		getBFS();
		
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<m;j++)
			{
				if(map[i][j] == 0)
				{
					result_cnt = -1;
				}
			}
		}
		
		System.out.println(result_cnt);
	}
	
	public static void getBFS()
	{
		int[] xx = {-1, 0, 1, 0};
		int[] yy = {0, 1, 0 ,-1};
		
		while(!t.isEmpty())
		{
			int tomato_size = t.size();		
			for(int i=0;i<tomato_size;i++)
			{
				int x = t.peek().x;
				int y = t.poll().y;
				
				for(int j=0;j<4;j++)
				{
					int ax = x+xx[j];
					int ay = y+yy[j];
					
					if(ax >=0 && ax < n && ay >=0 && ay < m)
					{
						if(map[ax][ay] == 0 && visit[ax][ay] == 0)
						{
							map[ax][ay] = 1;
							t.offer(new TomatoLocation(ax, ay));
							visit[ax][ay] = 1;
						}
					}
				}
			}
			
			result_cnt++;
		}		
	}

}

[Baekjoon][https://www.acmicpc.net/problem/5427]

너비 우선 탐색(BFS) 알고리즘

백준 #4179 불! 문제와 결국 동일한 문제이다.

풀이

상근이와 불의 위치를 Queue<MapLocation> 좌표값으로 담아두고 BFS 알고리즘을 호출한다.

불을 먼저 상, 하, 좌, 우 방향으로 1초마다 번지도록 처리한 후 (map[x][y] == '.' 인 경우에만)

상근이의 위치가 끝에 도달했는지 체크 후 도달하지 않았으면

위치를 map[x][y] =='.' && visit[x][y] = 0 (방문하지 않은 지역) 조건으로 이동 시킨다.

상근이의 위치가 사이드에 도달했으면 결과값을 ArrayList에 담은 후 

Test Case가 모두 완료되면 결과값을 모두 출력한다.

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

class MapLocation{
	int x;
	int y;
	
	public MapLocation(int x, int y) {
		// TODO Auto-generated constructor stub
		this.x = x;
		this.y = y;
	}
}

public class Main {

	static int tc = 0; // 테스트 케이스
	static char map[][];
	static int visit[][];
	static Queue<MapLocation> f;
	static Queue<MapLocation> sg;
	static int w;
	static int h;
	static int sec;
	
	static ArrayList<Object> result = new ArrayList<>();
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		Scanner sc= new Scanner(System.in);
		
		tc = sc.nextInt();
		
		for(int i=0;i<tc;i++) {
			sec = 0;
			w = sc.nextInt(); // 너비
			h = sc.nextInt(); // 높이
			
			f = new LinkedList<>();
			sg = new LinkedList<>();
			
			map = new char[h][w];
			visit = new int[h][w];
			
			for(int j=0;j<h;j++) {
				String str = sc.next();
				for(int k=0;k<w;k++) {
					map[j][k] = str.charAt(k);
					
					if(map[j][k] == '*') {
						f.offer(new MapLocation(j, k));
					}else if(map[j][k] == '@') {
						sg.offer(new MapLocation(j, k));
						visit[j][k] = 1;
					}
				}
			}
			
			getBFS();
		}
		
		for(int i=0;i<result.size();i++) {
			System.out.println(result.get(i));
		}
	}
	
	public static void getBFS() {
		int[] xx = {-1, 0, 1, 0};
		int[] yy = {0, 1, 0, -1};
		
		while(!sg.isEmpty()) {
			
			sec++;
			
			// 불 먼저 이동
			int fire_size = f.size();
			for(int i=0;i<fire_size;i++) {
				int x = f.peek().x;
				int y = f.poll().y;
				
				for(int j=0;j<4;j++) {
					int ax = x+xx[j];
					int ay = y+yy[j];
					
					if(ax >=0 && ax < h && ay >=0 && ay < w) {
						if(map[ax][ay] == '.' || map[ax][ay] == '@') {
							map[ax][ay] = '*';
							f.offer(new MapLocation(ax, ay));
						}
					}
				}
			}
			
			// 상근이
			int person = sg.size();
			for(int i=0;i<person;i++) {
				int x = sg.peek().x;
				int y = sg.poll().y;
				
				// 상근이의 위치가 가장자리면 종료
				if(x == 0 || y == 0 || x == h-1 || y == w-1) {
					result.add(sec);
					return;
				}
				
				for(int j=0;j<4;j++) {
					int ax = x+xx[j];
					int ay = y+yy[j];
					
					if(ax >= 0 && ax < h && ay >=0 && ay < w) {
						if(map[ax][ay] == '.' && visit[ax][ay] == 0) {
							map[ax][ay] = '@';
							sg.offer(new MapLocation(ax, ay));
						}
					}
				}
			}
		}
		
		result.add("IMPOSSIBLE");
	}
}

[Baekjoon][https://www.acmicpc.net/problem/4179]

너비 우선 탐색(BFS) 알고리즘

지훈이와 불의 위치를 Queue에 담고 BFS 알고리즘을 호출 해서 처리.

지훈이의 위치가 Queue에 존재할 때까지 BFS 알고리즘을 호출하며,

불의 위치 먼저 상, 하, 좌, 우로 1분마다 번지도록 처리한다.

지훈이의 위치는 visit[x][y] == 0 (방문하지 않은 위치) && map[x][y] == '.' 위치로만 이동이 가능하며,

끝자락에 도달했을 대의 분+1 값을 출력한다.

아래 이미지는 예제1의 1분마다 로직이 처리되었을때를 출력해보았다.

[예제 입력1]

4 4

########
#JF#
#..#
#..#

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

class Location{
	
	int x;
	int y;
	
	public Location(int x, int y) {
		// TODO Auto-generated constructor stub
		this.x = x;
		this.y = y;
	}
}

public class Main {

	static int r;
	static int c;
	static char map[][];
	static int minute = 0;
	static int visit[][];
	static Queue<Location> jh; // 지훈 좌표값
	static Queue<Location> f; // 불 좌표값
	static boolean flag = true;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		r = sc.nextInt(); // 높이
		c = sc.nextInt(); // 가로
		
		map = new char[r][c];
		visit = new int[r][c];
		jh = new LinkedList<>();
		f = new LinkedList<>();
		
		for(int i=0;i<r;i++) {
			String str = sc.next();
			for(int j=0;j<c;j++) {
				map[i][j] = str.charAt(j);
				
				if(map[i][j] == 'F') {
					f.offer(new Location(i, j));
				} else if(map[i][j] == 'J') {
					jh.offer(new Location(i, j));
					visit[i][j] = 1;
				}
			}
		}
		
		getBFS();
	}
	
	public static void getBFS()	{
		
		int[] xx = {-1, 0, 1, 0};
		int[] yy = {0, 1, 0, -1};
		
		while(!jh.isEmpty()) {
			int fire_size = f.size();
			
			for(int i=0;i<fire_size;i++) {
				int x = f.peek().x;
				int y = f.poll().y;
				
				for(int j=0;j<4;j++) {
					int ax = x+xx[j];
					int ay = y+yy[j];
					
					if(ax > 0 && ax < r && ay > 0 && ay < c) {
						if(map[ax][ay] == '.' || map[ax][ay] == 'J') {
							map[ax][ay] = 'F';
							f.offer(new Location(ax, ay));
						}
					}
				}
			}
			
			int person = jh.size();
			for(int i=0;i<person;i++) {
				int x = jh.peek().x;
				int y = jh.poll().y;
				
				if(x == 0 || x == r-1 || y == 0 || y == c-1) {
					minute++;
					System.out.println(minute);
					return;
				}
				
				for(int j=0;j<4;j++) {
					int ax = x + xx[j];
					int ay = y + yy[j];
					
					if(ax >= 0 && ax < r && ay >= 0 && ay < c) {
						if(map[ax][ay] == '.' && visit[ax][ay] == 0) {
							map[ax][ay] = 'J';
							jh.offer(new Location(ax, ay));
							visit[ax][ay] = 1;
						}
					}
				}
			}
		
			minute++;
		}
		
		if(flag) {
			System.out.println("IMPOSSIBLE");
		}
	}
}

[Baekjoon][https://www.acmicpc.net/problem/11724]

깊이 우선 탐색(DFS) 알고리즘

예제 입력 1 > 로 주어진 각 N개의 정점을 연결하는 간선을 아래 그림과 같이 표현할 수 있다.

[풀이]

연결된 노드를 map[정점1][정점2] = 1 로 주며, 해당 노드의 방문 여부는 visit[정점] 변수로 주어

DFS 알고리즘을 탐색하며 연결된 map[정점1][정점2] && visit[정점] = 0(방문하지 않은 정점)

조건으로 연결된 정점 탐색이 끝날때마다 결과를 +1 씩 증가해주도록 풀이했다.

(* map[정점2][정점1] 또한 연결된 값이므로 =1 처리)

또한, 정점이 3, 연결된 간선이 1개로 아래 그림과 같이 처리된 케이스 체크를 위해

방문하지 않은 visit[정점]=0 인 케이스를 체크해서 결과값 +1씩 처리하였다.

import java.util.Scanner;

public class Main {

	static int n;
	static int m;
	static int map[][];
	static int visit[];
	static int cnt = 0;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		m = sc.nextInt();
		map = new int[n+1][n+1];
		visit = new int[n+1];
		
		for(int i=0;i<m;i++)
		{
			int u = sc.nextInt();
			int v = sc.nextInt();
			
			map[u][v] = 1;
			map[v][u] = 1;
		}
		
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=n;j++) {
				if(map[i][j] == 1 && visit[j] == 0) {
					getDFS(i);
					cnt++;
				}
			}
		}
		
		for(int i=1;i<=n;i++) {
			if(visit[i] == 0) {
				cnt++;
			}
		}
		
		System.out.println(cnt);
	}
	
	public static void getDFS(int x)
	{
		visit[x] = 1;
		
		for(int i=1;i<=n;i++) {
			if(map[x][i] == 1 && visit[i] == 0) {
				getDFS(i);
			}
		}
	}
}