java 알고리즘 스터디 7주차 - 구현

19236 청소년 상어

📌문제 링크

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

📋코드

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

public class Main {
	// 4x4 크기 map을 사용하므로 N=4로 설정
	static int N = 4, res = 0;
	
	// 반시계 회전
	// ↑, ↖, ←, ↙, ↓, ↘, →, ↗ 
	static int[] dr = {-1, -1, 0, 1, 1, 1, 0, -1};
	static int[] dc = {0, -1, -1, -1, 0, 1, 1, 1};
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stk;
		
		int num=0, dir=0, sdir=0;
        // NxN map에 {물고기 번호, 방향} 저장
		int[][][] map = new int[N][N][2];
		
		for (int i = 0; i < N; i++) {
			stk = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				num = Integer.parseInt(stk.nextToken());
                // 입력값이 1부터 시작하므로 1을 빼줌
				dir = Integer.parseInt(stk.nextToken()) - 1;
				
				map[i][j][0] = num;
				map[i][j][1] = dir;
                
                // 맨 처음에 상어가 (0,0) 위치의 물고기를 먹음
				if (i ==0 && j == 0) {
					sdir = dir; // 상어가 처음에 가지는 방향
					map[i][j][0] = 0;
					res += num; // 먹은 물고기 번호
				}
				
			}
		}
		
        // 복사할 배열
		int[][][] tmp = new int[N][N][2];
		copyMap(map, tmp);
		dfs(0, 0, sdir, tmp, res);
		
		System.out.println(res);
	}

	// sr, sc : 상어의 위치, sdir : 상어의 방향, map : map 배열, sum : 지금까지 먹은 물고기 번호의 합
	private static void dfs(int sr, int sc, int sdir, int[][][] map, int sum) {
    	// 최댓값 갱신
		res = Math.max(res, sum);
		
        // 물고기 이동
        // sr, sc : 상어의 위치
		moveFish(sr, sc, map);
		
		int[][][] tmp = new int[N][N][2]; // 복사할 배열
        
        // 상어 이동
		int nr = sr, nc = sc;
		for (int i = 1; i < N; i++) {
			nr += dr[sdir];
			nc += dc[sdir];
			
            // 범위를 벗어나면 break
			if (!isValid(nr, nc)) break;
            // 물고기가 없으면 continue
			if (map[nr][nc][0] == 0) continue;
			
			copyMap(map, tmp); // 배열 복사
			tmp[sr][sc][0] = 0; // 상어의 이전 위치 0으로 초기화
			tmp[nr][nc][0] = -1; // 상어의 다음 위치 표시
			
            // dfs
			dfs(nr, nc, map[nr][nc][1], tmp, sum + map[nr][nc][0]);
		}
	}

	// 배열 복사
	private static void copyMap(int[][][] origin, int[][][] copy) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				copy[i][j][0] = origin[i][j][0];
				copy[i][j][1] = origin[i][j][1];
			}
		}
	}
    
    // 물고기 이동
	private static void moveFish(int sr, int sc, int[][][] map) {
		int nr, nc, ndir, dir;
		
		int[] idx = new int[2];
        // 번호가 작은 물고기부터 이동
		for (int i = 1; i < N*N+1; i++) {
        	// 물고기 위치 찾기
			idx = findFish(i, map);
            // 해당 번호의 물고기가 없다면 다음 번호 물고기 이동
			if (idx[0] == -1 && idx[1] == -1) continue;
			
            // 현재 물고기의 방향
			dir = map[idx[0]][idx[1]][1];
            
            // 방향 회전
			for (int j = 0; j < 8; j++) {
				ndir = (dir + j) % 8; // 회전한 방향
				nr = idx[0] + dr[ndir];
				nc = idx[1] + dc[ndir];
				
                // 범위를 벗어났거나 상어가 있는 위치면 반시계 회전
				if (!isValid(nr, nc) || (nr == sr && nc == sc)) continue;
				
                // 이동할 위치에 물고기가 없으면 그대로 이동
				if (map[nr][nc][0] == 0) {
					map[idx[0]][idx[1]][0] = 0; 
					map[nr][nc][0] = i;
					map[nr][nc][1] = ndir;
					
				} else {
                	// 이동할 위치에 물고기가 있다면 swap
					swap(idx[0], idx[1], ndir, nr, nc, map);
				}
				
				break;
			}
			
		}
	}
	
    // 물고기 위치 이동
	private static void swap(int i, int j, int dir, int nr, int nc, int[][][] map) {
		int num = map[i][j][0];
		
		map[i][j][0] = map[nr][nc][0];
		map[i][j][1] = map[nr][nc][1];
		
		map[nr][nc][0] = num;
		map[nr][nc][1] = dir;
	}

	private static int[] findFish(int num, int[][][] map) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j][0] == num) {
					return new int[] {i, j};
				}
			}
		}
		return new int[] {-1, -1};
	}

	private static boolean isValid(int nr, int nc) {
		if (nr < 0 || nr >= N || nc < 0 || nc >= N) return false;
		return true;
	}

}

⏱ 시간 복잡도

메모리 : 14252KB, 시간 : 128ms

20055 컨베이어 벨트 위의 로봇

📌문제 링크

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

📋코드

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

public class Main {
	static int N, K, cnt, step;
	static int[][] belt;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stk = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(stk.nextToken());
		K = Integer.parseInt(stk.nextToken());
		
        // 컨베이어 벨트
        // 2차원 배열로 {내구도, 로봇이 올라가있는지 여부} 저장
		belt = new int[2*N][2];
		
		stk = new StringTokenizer(br.readLine());
		for (int i = 0; i < 2*N; i++) {
        	// 내구도 저장
			belt[i][0] = Integer.parseInt(stk.nextToken());
		}
		
		
		int up = 0; // 올리는 위치
		int down = N-1; // 내리는 위치
		cnt = 0; // 0의 개수
		step = 0; // 단계
		while(cnt < K) {
			step++;
			
			// 한 칸 회전
			if (--up < 0) {
				up = 2*N-1;
			}
			
			if (--down < 0) {
				down = 2*N-1;
			}
			
			// 로봇 이동
			moveRobots(down);
			
			// 로봇 올리기
			if (belt[up][0] > 0) {
				belt[up][1] = 1;
				if (--belt[up][0] == 0) cnt++;
			}
			
		}
		
		System.out.println(step);
	}
	
	private static void moveRobots(int down) {
		// 내리는 위치 로봇 내리기
		belt[down][1] = 0;
		
		int cur = down, next;
		
		// 로봇 이동
		for (int i = 1; i < N; i++) {
			if (--cur < 0) {
				cur = 2*N-1;
			}
			next = (cur+1) % (2*N);
			// 지금 위치에 로봇이 올라가 있고, 다음 위치의 내구도가 0 이상이면서 올라가있는 로봇이 없을 때
			if (belt[cur][1] == 1 && belt[next][0] > 0 && belt[next][1] == 0) {
				belt[cur][1] = 0;
				belt[next][1] = 1;
				if (--belt[next][0] == 0) cnt++;
				
				// 로봇이 내리는 위치로 이동했다면 즉시 내림
				if (next == down) {
					belt[next][1] = 0;
				}
			}
			
			
		}
	}

}

⏱ 시간 복잡도

메모리 : 14384KB, 시간 : 244ms
처음에 회전을 쉽게 구현하기 위해서 컨베이어 벨트를 LinkedList로 풀었다가 1620ms가 나왔다.. 인덱스 접근에 O(N)만큼 걸려서 그렇게 나온 것 같다ㅠ
좌표로 벨트 회전을 구현하니 시간을 줄일 수 있었다.