사전 캠프 14일차

 

 

백준 16926 배열 돌리기 1

어제 풀다가 못푼 배열 돌리기 문제를 마무리 했다. 생각보다 시뮬레이션 문제는 많이 까다로운거 같다. 아이디어가 떠오르지 않으면 굉장히 힘든 문제였다.

public class Main {
	public static StringBuilder sb = new StringBuilder();
	public static int [][] arr;
	public static int [] arr2;
	public static int n;
	public static int count = 0;
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));	
		StringTokenizer st = new StringTokenizer(bf.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int r = Integer.parseInt(st.nextToken());
		arr = new int[n][m];
		for(int i=0;i<n;i++) {
			st = new StringTokenizer(bf.readLine());
			for(int j=0;j<m;j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		int count = Math.min(n, m)/2;
		for(int i=0;i<r;i++) {
			for(int j=0;j<count;j++) {
				int temp = arr[j][j];
				//윗줄
				for(int k=j+1;k<m-j;k++) {
					arr[j][k-1] = arr[j][k];
				}
				//오른쪽 줄
				for(int k=j+1;k<n-j;k++) {
					arr[k-1][m-j-1] = arr[k][m-j-1];
				}
				//아랫줄
				for(int k=m-j-2;k>=j;k--) {
					arr[n-j-1][k+1] = arr[n-j-1][k];
				}
				//왼쪽 줄
				for(int k=n-j-2;k>=j;k--) {
					arr[k+1][j] = arr[k][j];
				}
				arr[j+1][j] = temp;
			}
		}
		print(n,m);
		System.out.println(sb);
	}
	public static void print(int n, int m) {
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				sb.append(arr[i][j]+" ");
			}
			sb.append("\n");
		}
	}
}

 

 

15683번 감시

솔직히 이해도 제대로 못했다...

순열을 만들어서...뭐...돌리고...뭐....나중에 다시 풀자...

class Node{
	int x;
	int y;
	public Node(int x, int y) {
		this.x = x;
		this.y = y;
	}
}
public class Main {
	public static StringBuilder sb = new StringBuilder();
	public static int [][] arr;
	public static int [][] copyarr;
	public static LinkedList<Node> list = new LinkedList<>();
	public static int output [];
	public static int n;
	public static int m;
	public static int min = Integer.MAX_VALUE;
	public static int[] dx = {-1, 0, 1, 0}; // 상 우 하 좌 시계방향 순서 
	public static int[] dy = {0, 1, 0, -1};
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));	
		StringTokenizer st = new StringTokenizer(bf.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		arr = new int[n][m];
		for(int i=0;i<n;i++) {
			st = new StringTokenizer(bf.readLine());
			for(int j=0;j<m;j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
				if(arr[i][j]!=0 && arr[i][j]!=6) {
					list.add(new Node(i,j));
				}
			}
		}
		output = new int[list.size()];
		dfs(0);
		System.out.println(min);
	}
  public static void dfs(int dep) {
	  if(dep == list.size()) {
			copyarr = new int[n][m];
			for(int i = 0; i < arr.length; i++) {
				System.arraycopy(arr[i], 0, copyarr[i], 0, arr[i].length);
			}
						
			// cctv번호와 순열로 뽑혀진 방향에 맞는 상하좌우 방향 설정 
			for(int i = 0; i < list.size(); i++) {
				move(list.get(i), output[i]);
			}
			
			// 사각 지대 구하기 
			checkCount();

			return;
		}
		
		for(int i = 0; i < 4; i++) {
			output[dep] = i;
			dfs(dep+1);
		}
	}
	public static void move(Node cctv, int d) {
		int x = cctv.x;
		int y = cctv.y;
		int cctvNum = arr[x][y];

		if(cctvNum == 1) {
			if(d == 0) watch(cctv, 0); // 상 
			else if(d == 1) watch(cctv, 1); // 우 
			else if(d == 2) watch(cctv, 2); // 하  
			else if(d == 3) watch(cctv, 3); // 좌 
		} else if(cctvNum == 2) {
			if(d == 0 || d == 2) {
				watch(cctv, 0); watch(cctv, 2); // 상하 
			} else {
				watch(cctv, 1); watch(cctv, 3); // 좌우 
			}
		} else if(cctvNum == 3) {
			if(d == 0) {
				watch(cctv, 0); // 상우 
				watch(cctv, 1);
			} else if(d == 1) { 
				watch(cctv, 1); // 우하 
				watch(cctv, 2);
			} else if(d == 2) { 
				watch(cctv, 2); // 하좌 
				watch(cctv, 3);
			} else if(d == 3) { 
				watch(cctv, 0); // 좌상 
				watch(cctv, 3);
			}
		} else if(cctvNum == 4) {
			if(d == 0) {
				watch(cctv, 0); // 좌상우 
				watch(cctv, 1);
				watch(cctv, 3);
			} else if(d == 1) {
				watch(cctv, 0); // 상우하 
				watch(cctv, 1);
				watch(cctv, 2);
			} else if(d == 2) {
				watch(cctv, 1); // 좌하우 
				watch(cctv, 2);
				watch(cctv, 3);
			} else if(d == 3) {
				watch(cctv, 0); // 상좌하 
				watch(cctv, 2);
				watch(cctv, 3);
			}
		} else if(cctvNum == 5) { // 상우하좌
			watch(cctv, 0);
			watch(cctv, 1);
			watch(cctv, 2);
			watch(cctv, 3);
		}
	}
	public static void watch(Node cctv, int d) {
		Queue<Node> queue = new LinkedList<>();
		boolean[][] visited = new boolean[n][m];

		queue.add(cctv);
		visited[cctv.x][cctv.y] = true;

		while(!queue.isEmpty()) {
			int nx = queue.peek().x + dx[d];
			int ny = queue.poll().y + dy[d];

			// 범위를 벗어나거나 벽을 만나면 끝 
			if(nx < 0 || nx >= n || ny < 0 || ny >= m|| copyarr[nx][ny] == 6) { 
				break;
			}

			if(copyarr[nx][ny] == 0) { 
				copyarr[nx][ny] = -1; // 빈칸이라면 감시할 수 있다는 의미로 -1 
				queue.add(new Node(nx, ny));
			} else { // 다른 cctv가 있거나 이미 감시된 칸이라면 
				queue.add(new Node(nx, ny)); // 그냥 통과 
			}
		}
	}
	public static void checkCount() {
		int cnt = 0;
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				if(copyarr[i][j] == 0) {
					cnt++;
				}
			}
		}
		min = Math.min(min, cnt);
	}
}

 

 

15686번 치킨 배달

조합에 대해 배운 문제다. 

class Node{
	int x;
	int y;
	public Node(int x, int y) {
		this.x = x;
		this.y = y;
	}
}
public class Main {
    public static int[][] arr;
    public static List<Node> chicken = new LinkedList<>();
    public static List<Node> home = new LinkedList<>();
    public static int n;
    public static int m;
    public static int[] combi;
    public static int min = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        arr = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(bf.readLine());
            for (int j = 1; j <= n; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                if (arr[i][j] == 1) {
                    home.add(new Node(i, j));
                }
                if (arr[i][j] == 2) {
                    chicken.add(new Node(i, j));
                }
            }
        }
        combi = new int[m];
        dfs(0, 1);
        System.out.println(min);
    }

    public static void dfs(int l, int s) {
        if (l == m) {
            distanceCheck();
        } else {
            for (int i = s; i <= chicken.size(); i++) {
                combi[l] = i;
                dfs(l + 1, i + 1);
            }
        }
    }
    public static void distanceCheck() {
    	int totaldistance = 0;
    	for(Node h : home) {
    		int distance = Integer.MAX_VALUE;
    		for(int x : combi) {
    			Node c = chicken.get(x-1);
    			distance = Math.min(Math.abs(h.x-c.x) + Math.abs(h.y-c.y),distance);
    		}
    		totaldistance += distance;
    	}
    	min = Math.min(min, totaldistance);
    }
}