BangBang's Devlogs

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

문제

DFS 문제라고 생각하고 풀었는데 stackoverflow가 자꾸 떠서 다른 사람 풀이 참고하여 풀었다. (알고보니 구현 문제)

해결 방안

문제에서의 로봇 청소기 작동 방법에 맞춰서 구현해주면 된다.

while 두개를 이용하여 구현하였으며 코드를 보면 1, 2 조건에 따른 코드를 구현하였다. 

코드

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

// 로봇 청소기
// 청소하는 영역의 갯수를 구하는 프로그램
// 청소기는 바라보는 방향이 있음
// (r,c) r: 북쪽으로부터 떨어진 칸의 갯수, c: 서쪽으로부터 떨어진 칸의 갯수
// 현재 방향을 기준으로 왼쪽 방향부터 차례대로 탐색을 진행함
public class Main {

	static int N; // 세로 (3~50)
	static int M; // 가로 (3~50)
	static int[][] map;
	
	static int r; // 로봇청소기 좌표(r,c)
	static int c; 
	static int d; // 바라보는 방향 (0:북, 1:동, 2:남, 3:서)
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, 1, 0, -1};
	static int cleanSite = 0;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str;

		str = br.readLine();
		N = Integer.parseInt(str.split(" ")[0]);
		M = Integer.parseInt(str.split(" ")[1]);
		map = new int[N][M];
		
		str = br.readLine();
		r = Integer.parseInt(str.split(" ")[0]);
		c = Integer.parseInt(str.split(" ")[1]);
		d = Integer.parseInt(str.split(" ")[2]);
		
		StringTokenizer st;
		for(int i=0; i<N; i++) {
			str = br.readLine();
			st = new StringTokenizer(str, " ");
			for(int j=0; j<M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		// ========= 입력 끝 ==========
		
		cleaning();
		System.out.println(cleanSite);
	}
	
	static void cleaning() {
		
		int dirCnt = 0; 
		int nx,ny;
		boolean flag = true;
		
		while(flag) {
			// 1. 현재 위치 청소
			if(map[r][c] == 0) {
				map[r][c] = 2;
				cleanSite++;
			}
			
			// 2. 탐색
			while(true) {
				if(dirCnt == 4) {
					nx = r - dx[d];
					ny = c - dy[d];
					
					// d. 뒷칸이 벽인 경우 작동 멈춤
					if(map[nx][ny] == 1) {
						flag = false;
						break;
					}
					// c. 후진
					else if(map[nx][ny] == 2) {
						r = nx;
						c = ny;
						dirCnt = 0;
					}
				}
				
				d--;
				if(d == -1)
					d = 3;
				nx = r + dx[d];
				ny = c + dy[d];
				
				// a. 한칸 전진
				if(map[nx][ny] == 0) {
					dirCnt = 0;
					r = nx;
					c = ny;
					break;
				}
				// b. 2번으로 돌아감
				else {
					dirCnt++;
					continue;
				}
				
			}
		}
	}

}

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

문제

벽 3개 세우는 경우를 완전 탐색하고 벽이 3개 세워진 경우에 바이러스를 퍼트려서 최대 안전 구역 크기를 구해주는 문제이다.

생각보다 쉽게 풀려서 놀랐다. DFS + BFS 문제

해결 방안

1. 메인에서 지도값 입력받을 때 바이러스의 좌표를 저장할 수 있는 자료구조(여기서는 ArrayList 사용함)를 사용해준다. (나중에 BFS 탐색에서 Queue에 넣어줄 값)

2. DFS 탐색을 이용하여 벽이 3개가 추가된 경우를 완전탐색한다.(벽이 3개가 추가된 지도가 만들어진다.)

3. DFS 탐색의 기저 사례에 벽이 3개가 추가된 경우로 설정해주고 해당 경우마다 바이러스를 BFS 탐색을 이용하여 퍼트려준다.
3.1. 이 때, 해당 지도를 copy한 지도를 만들어준다. (기존 지도는 DFS를 통해 계속 사용해야하므로)
3.2. copy된 지도에 BFS 탐색을 이용하여 바이러스를 퍼트려준다.
3.3. 바이러스가 퍼트려진 copy된 지도의 안전 구역 크기를 구해준다.
3.4. 기존에 누적된 max 안전 구역 크기와 비교하여 새로운 max 안전 크기 구역을 구해준다.

4. 바이러스가 퍼지는 부분을 BFS를 이용하여 구해주었다. (3.2 부분)
4.1. 3.2 부분에서 바이러스를 퍼트릴때 1.에서 저장한 바이러스 좌표를 Queue에 넣어주고 visited를 true로 만들어준다.
4.2. 바이러스 좌표의 상하좌우 부분의 경우 범위가 지도 범위를 넘어가는지 확인해주고 방문 안했으며 빈 칸인 경우 바이러스를 확진 시켜준다.
4.3. BFS 탐색이 끝나면 해당 map을 반환해준다.
4.4. 끝나면 3.2 과정이 끝나 3.3 과정이 시작한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

// 연구소
// 바이러스 확산을 막기 위해서 연구소에 벽을 세우려고함
// NxM 직사각형의 연구소
// 바이러스는 인접한 빈칸(상하좌우)으로 모두 퍼져나감
// 새로 세울 수 있는 벽의 갯수는 3개
// 0:빈칸  1:벽  2:바이러스
// 안전 영역(바이러스, 벽 제외한 부분) 크기의 최댓값을 구하는 프로그램 작성
public class Main {

	static int N; // 세로 (3~8)
	static int M; // 가로 (3~8)
	static int[][] maps; // 지도
	static boolean[][] visited;
	
	// 바이러스 움직임 (상하좌우)
	static int[] dx = {-1, 1, 0, 0}; // 세로
	static int[] dy = {0, 0, -1, 1}; // 가로
	
	static List<int[]> virusLocation = new ArrayList<>(); // 바이러스 좌표
	
	static int max_safe = 0;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String str;
		str = br.readLine();
		N = Integer.parseInt(str.split(" ")[0]);
		M = Integer.parseInt(str.split(" ")[1]);
		
		maps = new int[N][M];
		visited = new boolean[N][M];
		
		StringTokenizer st;
		for(int i=0; i<N; i++) {
			str = br.readLine();
			st = new StringTokenizer(str, " ");
			for(int j=0; j<M; j++) {
				maps[i][j] = Integer.parseInt(st.nextToken());
				
				if(maps[i][j] == 2) {
					virusLocation.add(new int[] {i, j});
				}
			}
		}
		//====== 입력 끝 ========
		
		// 완전 탐색으로 3개의 벽 세우고 바이러스 퍼졌을 때 안전지역이 최대값을 찾는 프로그램
		dfs(0);
		
		
		System.out.println(max_safe);

	}
	
	public static int[][] copyMap() {
		int[][] copy_maps = new int[N][M];
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				copy_maps[i][j] = maps[i][j];
			}
		}
		
		return copy_maps;
	}
	
	//바이러스 퍼지는 것을 bfs로 구현
	public static int[][] bfs(int[][] copy_maps, boolean[][] visited) {
		
		Queue<int[]> q = new LinkedList<>();
		
		// 처음 바이러스좌표를 Queue에 넣어줌
		int[] loc = new int[2];
		for(int i=0; i<virusLocation.size(); i++) {
			loc = virusLocation.get(i);
			q.offer(new int[] {loc[0], loc[1]});
			visited[loc[0]][loc[1]] = true;
		}
		
		// 현재 바이러스 위치
		int cx, cy;
		int nx, ny;
		int[] tempLoc;
		while(!q.isEmpty()) {
			tempLoc = q.poll();
			cx = tempLoc[0];
			cy = tempLoc[1];
			
			// 상하좌우 바이러스 퍼트림
			for(int i=0; i<4; i++) {
				nx = dx[i] + cx;
				ny = dy[i] + cy;

				// 범위 넘어가는지 확인
				if(nx<0 || nx>=N || ny<0|| ny>=M) continue;
				
				// 방문 안했고 빈 칸 인지 확인해서 바이러스확진
				if(!visited[nx][ny]) {
					if(copy_maps[nx][ny] == 0) {
						visited[nx][ny] = true;
						copy_maps[nx][ny] = 2;
						q.offer(new int[] {nx, ny});
					}
				}
			}
		}
		
		return copy_maps;
	}
	
	public static void dfs(int cnt) {
		// 벽의 갯수가 3개가 됬을 때
		if(cnt == 3) {
			
			int[][] copy_maps = new int[N][M];
			
			// copy map
			copy_maps = copyMap();
			
			// 바이러스 다 퍼트리고
			boolean[][] visited = new boolean[N][M];
			copy_maps = bfs(copy_maps, visited);
			
			int safe = 0;
			// 안전 지역 갯수 구하고(빈 칸의 갯수)
			for(int i=0; i<N; i++) {
				for(int j=0; j<M; j++) {
					if(copy_maps[i][j] == 0)
						safe++;
				}
			}
			
			// 안전지역 최댓값 구함
			max_safe = Math.max(max_safe, safe);
		}
		else {
			
			// 벽의 갯수 dfs 탐색으로 늘려줌
			for(int i=0; i<maps.length; i++) {
				for(int j=0; j<maps[i].length; j++) {
					// 벽이나 바이러스일 경우 
					if(maps[i][j] == 1 || maps[i][j] == 2) continue;
					// 빈 칸 인 경우
					else {
						// 방문하지 않은 경우
						if(!visited[i][j]) {
							// 빈칸에 벽을 세워줌
							visited[i][j] = true;
							maps[i][j] = 1;
							dfs(cnt+1);
							maps[i][j] = 0;
							visited[i][j] = false;
						}
					}
				}
			}
		}
	}

}

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

문제

나는 DFS로 풀었다. 풀고나서 다른 사람들의 풀이를 보니 DP를 이용하여 푼 것을 확인하였다.
다음 복습에는 꼭 DP로 풀어봐야겠다.

해결 방안

1부터 N일 까지 상담이 가능하며 하루에 1개씩만 상담이 가능하다. 이 부분에서 걸리는 시간 비교를 통한 DFS를 이용하면 구할 수 있을 것이라고 생각하였다. 

1. DFS 탐색 시작 부분에서 반복문을 이용해서 1~N일까지 DFS 탐색을 하는데 i + T[i] 가 N+1이 넘어가는 순간은 제외하고 진행하였다. (문제에서 퇴직날까지 상담이 가능하다고 하였므르로)

2. 그리고 DFS 탐색 부분에서 기저 사례는 dfs 함수에서 보내준 index 값과 T[index]의 합이 N+1이 넘어가는 순간이다.
그 순간 최대값을 계속 갱신해준다.

3. 그외 DFS 탐색 부분에서는 dfs 함수에서 보내준 index 값에 T[index] 더한 수 부터 다시 DFS 탐색을 해준다.
이 때 기저사례로 빠질 수 있는 조건을 만들어준다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

// 퇴사
// N+1일 째 되는 날 퇴사
// 남은 N일 동안 최대한 많은 상담
// 하루에 상담 1개만 가능
public class Main {
	
	static int N; // 상담 가능 일수
	static int[] T; // 상담을 완료하는데 걸리는 시간
	static int[] P; // 상담을 했을 때 받을 수 있는 금액
	
	static int result = 0; // 최대 이익

	public static void main(String[] args) throws Exception, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		T = new int[N+1];
		P = new int[N+1];
		
		String str;
		for(int i=1; i<N+1; i++) {
			str = br.readLine();
			T[i] = Integer.parseInt(str.split(" ")[0]);
			P[i] = Integer.parseInt(str.split(" ")[1]);
		}
		
		int sum = 0;
		for(int i=1; i<N+1; i++) {
			sum = 0;
			if(i+T[i]<=N+1) {
				sum = P[i];
				dfs(i, sum);
			}
		}
		
		System.out.println(result);

	}
	
	public static void dfs(int index, int sum) {
		if(index + T[index] >= N+1) {
			result = Math.max(result, sum);
		}
		else {
			for(int i = index+T[index]; i<N+1; i++) {
				if(i+T[i]<=N+1) {
					sum += P[i];
					dfs(i, sum);
					sum -= P[i];
				}
				else {
					dfs(i, sum);
				}
			}
		}
	}

}

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

문제

쉬운듯 안쉬운듯... 처음 풀기엔 어려웠다... 다른사람의 풀이를 많이 참고함

해결 방안

최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록값을 구하는 문제로써 5의 깊이를 가지는 DFS를 이용하여 문제를 풀어야겠다고 생각하였다.

1-1. 일단 기저사례에 도달하였을 때 해당 board의 가장 큰 값을 구하고
그 값과 지금까지 깊이가 5가 됬을 때 board의 가장 큰 값의 max 값을 비교한다.

1-2. DFS 탐색 부분은
상하좌우 모든 방면으로 이동시켜준다. 이때 board를 가지고 값들을 이동(merge()시켜주고 전의 값들을 copyBoard에 저장해둬서 반환 했을때 다시 board에 copyBoard 값을 저장해준다.

2. merge() 하는 부분은 Queue 자료구조를 이용하였다. 세로, 가로를 구분하여 한 줄 씩 해결하였다.
Queue 에 한 줄의 값중 0이 아닌 숫자들을 다 넣어준 다음
Queue에 있는 값들을 꺼내가면서 조건 3가지에 따라 board에 Queue에서 빼준 값을 다시 넣어주었다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

// 2048 (Easy)
// 최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력
public class Main {

	static int n; //(1~20)
	static int[][] board; //게임판
	static int result; // 가장 큰 블록
	
	public static void main(String[] args) throws IOException {
		
		// 입력
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		
		board = new int[n][n];
		
		String str;
		StringTokenizer st;
		for(int i=0; i<n; i++) {
			str = br.readLine();
			st = new StringTokenizer(str, " ");
			
			for(int j=0; j<n; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		result = 0;
		dfs(0);
		
		System.out.println(result);

	}
	
	static void dfs(int depth) {
		if(depth>=5) {
			// 게임 판 가장 큰 블록 찾기
			int max = getMaxValue();
			// 최대값 찾아서 비교
			result = Math.max(result, max);
			return;
		}
		else {
			// 복사
			int[][] copyBoard = new int[n][n];
			copyBoard(copyBoard, board);
			
			for(int i=1; i<=4; i++) {
				merge(i);
				dfs(depth+1);
				copyBoard(board, copyBoard);
				
			}
		}
	}
	
	static void copyBoard(int[][] a, int[][] b) {
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				a[i][j] = b[i][j];
			}
		}
	}
	
	// 게임판에서 가장 큰 값 찾기
	static int getMaxValue() {
		int max = 0;
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				max = Math.max(max, board[i][j]);
			}
		}
		
		return max;
	}
	
	// 
	static void merge(int dir) {
		
		Queue<Integer> q = new LinkedList<>();
		
		switch(dir) {
			// 상
			case 1:
				for(int i=0; i<n; i++) {
					// 세로 한줄 씩 해결
					for(int j=0; j<n; j++) {
						// 0이 아닌 경우 q에 넣어주고
						if(board[j][i]!=0) q.offer(board[j][i]);
						board[j][i] = 0;
					}
					
					// q에는 세로줄이 다 넣어진 상태
					// q에서 꺼내면서 합쳐줄껀 합쳐주고 board에 저장
					int index = 0;
					int popData;
					while(!q.isEmpty()) {
						popData = q.poll();
						
						// 0일 때 (아무것도 안들어간 상태)
						if(board[index][i] == 0) {
							board[index][i] = popData;
						}
						// 같을 때
						else if(board[index][i] == popData) {
							board[index][i] = popData*2;
							index++;
						}
						// 들어가있을 때 (다음거에 데이터 넣어줌)
						else {
							index++;
							board[index][i] = popData;
						}
					}
				}
				break;
				
			// 하
			case 2:
				for(int i=0; i<n; i++) {
					// 세로 한줄 씩 해결(밑줄부터)
					for(int j=n-1; j>=0; j--) {
						// 0이 아닌 경우 q에 넣어주고
						if(board[j][i]!=0) q.offer(board[j][i]);
						board[j][i] = 0;
					}
					
					// q에는 세로줄이 다 넣어진 상태
					// q에서 꺼내면서 합쳐줄껀 합쳐주고 board에 저장
					int index = n-1;
					int popData;
					while(!q.isEmpty()) {
						popData = q.poll();
						
						// 0일 때 (아무것도 안들어간 상태)
						if(board[index][i] == 0) {
							board[index][i] = popData;
						}
						// 같을 때
						else if(board[index][i] == popData) {
							board[index][i] = popData*2;
							index--;
						}
						// 들어가있을 때 (다음거에 데이터 넣어줌)
						else {
							index--;
							board[index][i] = popData;
						}
					}
				}
				break;
				
			// 좌
			case 3:
				for(int i=0; i<n; i++) {
					// 가로 한줄 씩 해결
					for(int j=n-1; j>=0; j--) {
						// 0이 아닌 경우 q에 넣어주고
						if(board[i][j]!=0) q.offer(board[i][j]);
						board[i][j] = 0;
					}
					
					// q에는 가로줄이 다 넣어진 상태
					// q에서 꺼내면서 합쳐줄껀 합쳐주고 board에 저장
					int index = n-1;
					int popData;
					while(!q.isEmpty()) {
						popData = q.poll();
						
						// 0일 때 (아무것도 안들어간 상태)
						if(board[i][index] == 0) {
							board[i][index] = popData;
						}
						// 같을 때
						else if(board[i][index] == popData) {
							board[i][index] = popData*2;
							index--;
						}
						// 들어가있을 때 (다음거에 데이터 넣어줌)
						else {
							index--;
							board[i][index] = popData;
						}
					}
				}
				break;
				
			// 우
			case 4:
				for(int i=0; i<n; i++) {
					// 가로 한줄 씩 해결
					for(int j=0; j<n; j++) {
						// 0이 아닌 경우 q에 넣어주고
						if(board[i][j]!=0) q.offer(board[i][j]);
						board[i][j] = 0;
					}
					
					// q에는 가로줄이 다 넣어진 상태
					// q에서 꺼내면서 합쳐줄껀 합쳐주고 board에 저장
					int index = 0;
					int popData;
					while(!q.isEmpty()) {
						popData = q.poll();
						
						// 0일 때 (아무것도 안들어간 상태)
						if(board[i][index] == 0) {
							board[i][index] = popData;
						}
						// 같을 때
						else if(board[i][index] == popData) {
							board[i][index] = popData*2;
							index++;
						}
						// 들어가있을 때 (다음거에 데이터 넣어줌)
						else {
							index++;
							board[i][index] = popData;
						}
					}
				}
				break;
		
		}
	}

}

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

문제

해결 방안

문제 전체 다 꼼꼼히 읽어봐야하는 Simulation(구현) 문제이다.

먼저 크게 1. 전체 입력 받는 부분 2. 게임 돌아가는 부분 두 가지로 나누어서 생각을 해봤다.

1. 전체 입력 받는 부분

1-1 보드의 크기
사과의 위치가 행, 열 그대로 주어져서 N+1 x N+1로 설정하였다.

1-2 사과의 위치
보드 위치 위에 사과가 있는 경우 1을 저장해주었다. (board[row][col] = 1)

1-3 뱀의 방향 정보
HashMap 자료구조를 이용하여 key에 시간을 넣어주고 value에 방향값을 넣어줘서 나중에 key값이 있는지 쉽게 찾을 수 있게 하였다.

2. 뱀 게임이 돌아가는 부분

시간에 따른 반복문을 돌게 하였다. 즉 while 안은 1초동안 이뤄지는 일들이다.
index 값을 이용하여 뱀의 머리가 진행할 방향을 설정해주었다.
초깃값은 index=0으로 오른쪽 방향이다.(dx[0], dy[0])
index=0 오른쪽 // index=1 아래 // index=2 왼쪽 //index=3 위
2-5에서 오른쪽으로 방향을 틀면 index++ 이고 왼쪽으로 방향을 틀면 index--가 될것이다.

2-1 다음 움직임 설정
nx, ny를 이용하여 현재 위치에 머리가 진행할 방향으로 이동해준다.
nx = cx + dx[index]
ny = cy + dy[index]

2-2 다음 움직임에 따른 게임이 끝나는지 확인
2-2-1 nx, ny가 벽에 부딪히는 경우(범위 넘어가는 경우)를 확인해준다.
2-2-2 nx, ny가 자기 몸통에 부딪힌 경우를 확인해준다.(snake 몸통 정보 확인)

2-3 보드에 사과 유무에 따른 일 수행
2-3-1 사과 있을 때 머리만 늘어난다.
2-3-2 사과 없을 때 머리는 늘어나고 꼬리는 줄어든다.

2-4 현재 움직임에 다음 움직임 저장

2-5 뱀의 방향 이동 정보가 있는지 확인하고 있으면 방향 설정
해당 시간이 HashMap key값에 있는지 확인하고 방향을 새로 설정해준다. 

자세한 것은 코드 주석과 비교하며 코드를 참고하면 된다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

// 뱀
// NxN 정사각형 보드
// 맨위 맨 위측 위치(1,1), 처음 오른쪽 방향을 향함
// 뱀은 계속 머리쪽이 늘어남
// 사과 있으면 사과 없어지고 머리 늘려서 꼬리 그대로
// 사과 없으면 머리 늘려서 꼬리가 위치한 칸 비워줌
public class Main {

	static int n; // 보드의 크기 (2~100)
	static int k; // 사과의 갯수 (0~100)
	static int l; // 뱀의 방향 변환 횟수 (1~100)
	static int time; // 게임 시간
	static int[][] board;
	
	static List<int[]> snake; //뱀의 몸통 위치 (x,y)
	
	// 처음 시작은 오른쪽 방향을 보고 있음
	// 0:오른쪽   1:아래쪽   2:왼쪽   3:위
	// D(오른쪽)가 다오면 index++
	// L(왼쪽)이 나오면 index--
	static int index = 0;
	static int[] dx = {0, 1, 0, -1}; //세로
	static int[] dy = {1, 0, -1, 0}; //가로
	
	static Map<Integer, String> dir; // 뱀의 방향 정보
	
	public static void main(String[] args) throws Exception, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		n = Integer.parseInt(br.readLine());
		k = Integer.parseInt(br.readLine());
		
		// 1,1이 맨 위 맨 좌측
		board = new int[n+1][n+1];
		
		// 사과 위치 입력
		String str;
		int row; // 행
		int col; // 열
		for(int i=0; i<k; i++) {
			str = br.readLine();
			
			row = Integer.parseInt(str.split(" ")[0]);
			col = Integer.parseInt(str.split(" ")[1]);
			
			board[row][col] = 1;
		}
		
		// 뱀 방향 정보 입력
		dir = new HashMap<>();
		l = Integer.parseInt(br.readLine());
		for(int i=0; i<l; i++) {
			str = br.readLine();
			int timeInfo = Integer.parseInt(str.split(" ")[0]);
			String directionInfo = str.split(" ")[1];
			
			dir.put(timeInfo, directionInfo);
		}
		
		// 뱀 시작 지점 (1,1) (x,y)
		snake = new LinkedList<>();
		snake.add(new int[]{1,1});
		
		time = 0;
		int nx, ny; // 다음 움직임
		int cx, cy; // 현재 움직임(1,1)
		cx = 1;
		cy = 1;
		// 뱀 움직임 시작
		while(true) {
			time++;
			
			// 다음 움직임(머리 데이터)
			nx = cx + dx[index];
			ny = cy + dy[index];
			
			// 끝나는지 확인
			if(isFinish(nx,ny)) break;
			
			// 사과 있는지 확인
			// 사과 있으면 사과 없어지고 머리 늘려서 꼬리 그대로
			if(board[nx][ny] == 1) {
				board[nx][ny] = 0;
				snake.add(new int[] {nx,ny}); // 머리 정보 추가
			}
			// 사과 없으면 머리 늘려서 꼬리가 위치한 칸 비워줌
			else {
				snake.add(new int[] {nx,ny}); // 머리 정보 추가
				snake.remove(0); // 꼬리 index는 0
			}
			 
			cx = nx;
			cy = ny;
			
			// 해당 시간 끝났을 때 다음 방향 정해주기
			if(dir.containsKey(time)) {
				// D(오른쪽)가 다오면 index++
				if(dir.get(time).equals("D")) {
					index++;
					if(index == 4)
						index = 0;
				}
				// L(왼쪽)이 나오면 index--				
				if(dir.get(time).equals("L")) {
					index--;
					if(index == -1)
						index = 3;
				}
				
			}
		}
		
		System.out.println(time);
	}
	
	// 게임이 끝나는지 확인
	static boolean isFinish(int nx, int ny){
		
		// 벽에 부딪히거나
		if(nx<1 || ny<1 || nx>=n+1 || ny>=n+1) 
			return true;
		
		// 자기 몸통에 닿거나
		for(int i=0; i<snake.size(); i++) {
			if(nx == snake.get(i)[0] && ny == snake.get(i)[1]) 
				return true;
		}
		
		return false;
	}

}

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

문제

N x M 종이 위에 5가지 도형 중 1가지를 놓아서 해당 도형이 놓인 칸에 있는 수들의 최대 값을 출력하는 문제이다.

해결 방안

1. ㅜ 모양으로 생긴 도형 외 4가지는 dfs를 이용하여 구할 수 있다.

- 위와 같이 ㅜ 모양을 제외한 4가지 도형의 각각의 모든 경우(회전, 대칭 포함)은 depth가 4인 DFS 탐색 모양이다. 
- depth가 4일때 최댓값을 구해준다.

2. ㅜ 모양으로 생긴 도형의 경우는 4가지 경우(ㅜ, ㅗ, ㅓ, ㅏ)가 있으므로 해당 경우를 완전 탐색 해준다. 
(가운데 튀어나온 경우 되돌아가야하므로 DFS탐색을 할 수 없다.)

3. 두 가지 경우의 최댓값을 구해준다.

코드

import java.util.Scanner;

// 테트로미노
// 테트로미노 5가지 모양(회전, 대칭 가능)
// N X M 종이 위에 테트로미노를 하나 놓으려고 함
// 각각의 칸에는 정수가 하나 쓰여있음
// 테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여있는 수들의 합을 최대로 하는 프로그램
public class Main {

	static int n; // 세로크기
	static int m; // 가로크기
	static int[][] maps;
	static boolean[][] checked;
	static int result = 0;
	
	// 왼쪽 오른쪽 위 아래 순으로 한칸 움직였을 때
	static int[] dx = {0, 0, -1, 1}; // 세로
	static int[] dy = {-1, 1, 0, 0}; // 가로
	
	// ㅜ 일때 모든 경우 (ㅜ,ㅗ,ㅓ,ㅏ 순)
	static int[][] ex = {{0, 0, 0, 1}, {1, 1, 1, 0}, {0, 1, 2, 1}, {0, 1, 2, 1}}; //세로
	static int[][] ey = {{0, 1, 2, 1}, {0, 1, 2, 1}, {1, 1, 1, 0}, {0, 0, 0, 1}}; //가로
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner input = new Scanner(System.in);
		
		n = input.nextInt();
		m = input.nextInt();
		maps = new int[n][m];
		checked = new boolean[n][m];
		
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				maps[i][j] = input.nextInt();
			}
		}
		
		// 4가지는 dfs (depth=4인)
		// ㅜ 모양은 따로 구해줌
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				
				// 4가지 모양
				checked[i][j] = true;
				dfs(i, j, maps[i][j], 1);
				checked[i][j] = false;
				
				// ㅜ 모양
				exceptionCase(i, j);
			}
		}
		
		System.out.println(result);
		
	}
	
	// ㅜ를 제외한 4가지 경우 (dfs를 이용하여 모든 경우를 만들 수 있음)
	static void dfs(int x, int y, int sum, int depth) {
		if(depth >= 4) {
			result = Math.max(result, sum);
			return;
		}
		else {
			int nx, ny;
			// 지금 방향에서 왼쪽 오른쪽 위 아래 방향으로 1칸 움직임
			for(int i=0; i<4; i++) {
				nx = x + dx[i]; // 세로
				ny = y + dy[i]; // 가로
				
				// 종이 범위 넘어가는지 확인
				if(nx<0 || nx>=n || ny<0 || ny>=m) continue;
				
				// 방문한적 없으면
				if(!checked[nx][ny]) {
					checked[nx][ny] = true;
					dfs(nx, ny, (sum+maps[nx][ny]), depth+1);
					
					// 체크 해제
					checked[nx][ny] = false;
				}
			}
		}
	}
	
	// ㅜ,ㅗ,ㅓ,ㅏ 모양 검사
	static void exceptionCase(int x, int y) {
		int nx, ny, sum;
		boolean outCheck = false;
		
		for(int i=0; i<4; i++) {
			sum = 0;
			outCheck = false;
			for(int j=0; j<4; j++) {
				nx = x + ex[i][j]; // 세로
				ny = y + ey[i][j]; // 가로
				
				// 종이 범위 넘어가는지 체크
				if(nx<0 || nx>=n || ny<0 || ny>=m) {
					outCheck = true;
					continue;
				}
				
				sum += maps[nx][ny];
			}
			
			// 범위 안나갔으면
			if(!outCheck)
				result = Math.max(sum, result);
		}
	}

}

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

문제

해결방안

구현 문제이다. 주사위가 굴러갈때마다 지도의 좌표와 주사위를 계속 바꿔주면 된다. 

1. 좌표의 경우 동쪽, 서쪽인 경우 y값을 변화시켜주고 이 때 지도의 범위에서 넘어가는지 확인하는 과정이 필요하다.

1-1. 지도에서 넘어갈 경우 해당 명령을 무시하고 넘어가면 된다.

1-2. 지도에서 넘어가지 않는 경우 문제에 주어진 과정을 구현해주면 된다.
(주사위를 굴렸을 때, 이동한 칸에 쓰여 있는 수가 0이면, 주사위의 바닥면에 쓰여 있는 수가 칸에 복사된다. 0이 아닌 경우에는 칸에 쓰여 있는 수가 주사위의 바닥면으로 복사되며, 칸에 쓰여 있는 수는 0이 된다. 주사위를 놓은 곳의 좌표와 이동시키는 명령이 주어졌을 때, 주사위가 이동했을 때 마다 상단에 쓰여 있는 값을 출력한다.)

2. 주사위 경우 항상 주사위의 밑면 index는 6이고 윗면은 1이고 그 외는 주사위의 전개도를 참고한다.
동서남북으로 굴러갈때 굴러간 주사위 면의 값들을 각 주사위 index에 저장해준다.

코드

import java.util.Scanner;

// 주사위 굴리기
// NxM 지도
// 지도의 오른쪽은 동쪽, 위쪽은 북쪽
// 지도의 좌표 (r,c) 
// r: 북쪽으로부터 떨어진 칸의 갯수
// c: 서쪽으로부터 떨어진 칸의 갯수

public class Main {

	static int n; // 지도의 세로크기 (x)
	static int m; // 지도의 가로크기 (y)
	static int x,y; // 주사위를 놓은 곳의 좌표
	static int k; // 명령의 갯수
	static int[][] maps;
	static int[] dice;
	static int[] tempDice;
	
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		n = input.nextInt();
		m = input.nextInt();
		x = input.nextInt();
		y = input.nextInt();
		k = input.nextInt();

		dice = new int[7];
		
		maps = new int[n][m];
		for(int i=0; i<maps.length; i++) {
			for(int j=0; j<maps[i].length; j++) {
				maps[i][j] = input.nextInt();
				
				// 처음 시작일때(x,y) 밑면이 6
				if(x==i && y==j) {
					if(maps[x][y] == 0)
						maps[x][y] = 0;
					else {
						dice[6] = maps[x][y];
						maps[x][y] = 0;
					}
				}
			}
		}
		
		int command;
		for(int i=0; i<k; i++) {
			command = input.nextInt();
			rollTheDice(command);
		}
	}
	
	// 주사위 굴리기
	// 동:1, 서:2, 북:3, 남:4
	// 범위 넘어가면 명령 무시
	// 아니면 주사위의 윗 면에 써있는 수를 출력(dice[1]);
	public static void rollTheDice(int command) {
		tempDice = dice.clone();
		boolean flag = true;
		
		if(command == 1) {
			if(y+1 < m) {
				y+=1;
				
				dice[1] = tempDice[4];
				dice[2] = tempDice[2];
				dice[3] = tempDice[1];
				dice[4] = tempDice[6];
				dice[5] = tempDice[5];
				dice[6] = tempDice[3];
			}
			else
				flag = false;
		}
		else if(command == 2) {
			if(y-1 >= 0) {
				y-=1;
				
				dice[1] = tempDice[3];
				dice[2] = tempDice[2];
				dice[3] = tempDice[6];
				dice[4] = tempDice[1];
				dice[5] = tempDice[5];
				dice[6] = tempDice[4];
			}
			else
				flag = false;
		}
		else if(command == 3) {
			if(x-1 >= 0) {
				x-=1;
				
				dice[1] = tempDice[5];
				dice[2] = tempDice[1];
				dice[3] = tempDice[3];
				dice[4] = tempDice[4];
				dice[5] = tempDice[6];
				dice[6] = tempDice[2];
			}
			else
				flag = false;
		}
		else if(command == 4) {
			if(x+1 < n) {
				x+=1;
				
				dice[1] = tempDice[2];
				dice[2] = tempDice[6];
				dice[3] = tempDice[3];
				dice[4] = tempDice[4];
				dice[5] = tempDice[1];
				dice[6] = tempDice[5];
			}
			else
				flag = false;
		}
		else {
			;
		}
		
		if(flag) {

			// 지도 좌표가 0인 경우 dice에 적힌 수가 지도 좌표에 적힌 값이 됨
			// 주사위의 젤 밑부분인 dice[6]이 지도 좌표에 적힌 값이 됨
			if(maps[x][y] == 0)
				maps[x][y] = dice[6];
			else {
				dice[6] = maps[x][y];
				maps[x][y] = 0;
			}

			// 그 윗부분인 dice[1]을 출력
			System.out.println(dice[1]);
		}
	}

}

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

문제

해결 방안

문제를 이해하고 단순히 구현하는 문제이다.
1. 총 감독은 시험장마다 1명씩 있어서 시험자 응시자 수 배열 a[]에서 b(총감독이 맡을 수 있는 응시자 수)만큼 다 빼주고 cnt++해주고 시작하였다.

2. b만큼 빼준 a[i] 값이 0보다 작거나 같으면 부감독이 필요없으므로 continue 해줬다.

3. 그렇지 않는 경우 a[i]를 c(부감독이 맡을 수 있는 응시자 수)로 나눠주고 몫을 cnt에 더해줬다.

4. a[i]를 c로 나누었을 때 나머지 값이 0보다 큰 경우 부 감독이 한명 더 필요하므로 cnt++를 해줫다.

코드

import java.util.Scanner;

// 시험 감독
public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner input = new Scanner(System.in);
		int n = input.nextInt();
		long cnt = 0; // 감독관 수
		int[] a = new int[n]; // 응시자 수
		
		for(int i=0; i<n; i++) {
			a[i] = input.nextInt();
		}
		
		int b = input.nextInt(); // 총감독이 맡을 수 있는 사람수
		int c = input.nextInt(); // 부감독이 맡을 수 있는 사람수
		
		for(int i=0; i<n; i++) {
			a[i]-=b;
			cnt++;
			
			// 총 감독이 맡을 수 있는 경우는 부감독 필요 없으므로 넘어감
			if(a[i]<=0) {
				continue;
			}
			// 부감독이 추가로 필요한 경우
			else {
				cnt += a[i]/c;
				// 나머지가 0보다 크면 부감독 한명 더 추가
				if(a[i]%c > 0) {
					cnt++;
				}
			}
		}
		
		System.out.println(cnt);
	}

}