25/02/20 (목)
목, 금, 월은 알고리즘 문제만 푸는 날이라고 합니다.
물론 쉬는날은 아니지만 조금 쉬는 날이라고 생각하고 여유롭게 풀어보겠습니다.
어제는 스파링에서 거의 이길뻔했는데 시간이 끝나서 마무리하지 못했습니다.
1. 실습
1) 백준
https://www.acmicpc.net/problem/1600
https://www.acmicpc.net/problem/14502
https://www.codetree.ai/frequent-problems/problems/ancient-ruin-exploration/description
2) G3_1600_말이 되고픈 원숭이 (BFS)
package basic.Ch22_문제풀기;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;
// 가중치가 없는 최소값, 최단경로 <= bfs()
// 말처럼 움직이는 횟수 K 제한
// 어느 특정 좌표에서 상하좌우 똔 말 처럼 움직이는 2가지를 고려
// bfs() 처리 visit 를 K 고려한 고민
public class G3_1600_말이되고픈원숭이_풀이 {
static int K, W, H;
static int[][] map;
// visit 처리는 동일 좌표 방문 시, 이후 동일한 상황 반복되기 때문, 이 문제는 같은 좌표라 하더라도 K 값이 얼마나에 딸라 이후 상황 달라질 수 있다.
// 3차원 배열 <= 좌표[][] + K
static boolean[][][] visit;
// 상,하,좌,우
static int[] dy = { -1, 1, 0, 0 };
static int[] dx = { 0, 0,-1, 1 };
// 말 움직임 8방
static int[] hdy = { -2, -2, -1, -1, 2, 2, 1, 1 };
static int[] hdx = { -1, 1, -2, 2, -1, 1, -2, 2 };
// bfs queue
static Queue<Node> queue = new ArrayDeque<>();
static class Node{
int y, x, k, d;
Node(int y, int x, int k, int d){
this.y = y; this.x = x; this.k = k; this.d = d;
}
}
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
K = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
W = Integer.parseInt(st.nextToken());
H = Integer.parseInt(st.nextToken());
map = new int[H][W];
visit = new boolean[H][W][K + 1]; // K 표현 : 0 ~ K
for (int i = 0; i < H; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < W; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
bfs();
}
static void bfs() {
// 시작점 좌표, K 이용 큐에 담는다. visit 도 함께
visit[0][0][K] = true;
queue.offer(new Node(0, 0, K, 0));
while( ! queue.isEmpty() ) {
Node node = queue.poll();
// 목표 도달?
if( node.y == H - 1 && node.x == W - 1) {
System.out.println(node.d); // 도달
return; // 종료
}
// 탐색 1 - 상하좌우
for (int i = 0; i < 4; i++) {
int ny = node.y + dy[i];
int nx = node.x + dx[i];
if( ny < 0 || nx < 0 || ny >= H || nx >= W || map[ny][nx] == 1 || visit[ny][nx][node.k] ) continue;
visit[ny][nx][node.k] = true;
queue.offer(new Node(ny, nx, node.k, node.d + 1)); // K 사용 X
}
// 탐색 2 - 말처럼 8방 ( 단 K 를 사용할 수 있으면 )
if( node.k == 0 ) continue;
for (int i = 0; i < 8; i++) {
int ny = node.y + hdy[i];
int nx = node.x + hdx[i];
if( ny < 0 || nx < 0 || ny >= H || nx >= W || map[ny][nx] == 1 || visit[ny][nx][node.k - 1] ) continue; // K 사용 O
visit[ny][nx][node.k - 1] = true; // K 사용 O
queue.offer(new Node(ny, nx, node.k - 1, node.d + 1)); // K 사용 O
}
}
System.out.println(-1);
}
}- 너무 어렵네요.. BFS는 조금 더 연습해야겠습니다
3) G4_14502_연구소 (DFS, BFS)
package basic.Ch22_문제풀기;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;
public class G4_14502_연구소 {
static int N, M, result;
static int[][] lab;
static int[] dy = {-1,1,0,0};
static int[] dx = {0,0,-1,1};
static Queue<Node> queue = new ArrayDeque<>();
static class Node{
int y, x;
Node(int y, int x){
this.y = y; this.x = x;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
lab = new int[N][M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine()," ");
for (int j = 0; j < M; j++) {
lab[i][j] = Integer.parseInt(st.nextToken());
}
}
wall(0);
System.out.println(result);
}
public static void wall(int n){
if(n == 3){
virus();
return;
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if(lab[i][j] == 0){
lab[i][j] = 1;
wall(n+1);
lab[i][j] = 0;
}
}
}
}
public static void virus(){
queue = new ArrayDeque<Node>();
int lab2[][] = new int[N][M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
lab2[i][j] = lab[i][j];
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if(lab2[i][j] == 2){
queue.offer(new Node(i, j));
}
}
}
while(!queue.isEmpty()) {
Node node = queue.poll();
for (int i = 0; i < 4; i++) {
int ny = node.y + dy[i];
int nx = node.x + dx[i];
if(ny >= 0 && ny < N && nx >= 0 && nx < M && lab2[ny][nx] == 0){
queue.offer(new Node(ny, nx));
lab2[ny][nx] = 2;
}
}
}
isSafe(lab2);
}
public static void isSafe(int[][] lab2){
int safe = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if(lab2[i][j] == 0){
safe++;
}
}
}
if(result < safe) result = safe;
}
}
4) 고대 문명 유적 탐사
import java.io.*;
import java.util.*;
public class Main {
// 격자판의 크기 (5x5)
static final int SIZE = 5;
// 현재 격자판의 상태를 저장하는 배열
static int[][] map = new int[SIZE][SIZE];
// 회전 및 제거 연산을 시뮬레이션하기 위한 임시 배열
static int[][] copyMap = new int[SIZE][SIZE];
// 8방향 이동을 위한 방향 배열 (회전 연산에 사용)
static int[] dc = {-1, -1, -1, 0, 1, 1, 1, 0}; // 열 방향 이동
static int[] dr = {-1, 0, 1, 1, 1, 0, -1, -1}; // 행 방향 이동
// 상하좌우 4방향 이동을 위한 방향 배열 (BFS 탐색에 사용)
static int[] dx = {0, 1, 0, -1}; // 열 방향 이동
static int[] dy = {-1, 0, 1, 0}; // 행 방향 이동
// 제거된 숫자를 채우기 위한 새로운 숫자들을 저장하는 큐
static Queue<Integer> q;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int k = Integer.parseInt(st.nextToken()); // 시뮬레이션 반복 횟수
int m = Integer.parseInt(st.nextToken()); // 채울 숫자의 개수
StringBuilder sb = new StringBuilder();
q = new LinkedList<>();
// 초기 격자판 상태 입력
for (int r = 0; r < SIZE; r++) {
st = new StringTokenizer(br.readLine());
for (int c = 0; c < SIZE; c++) {
map[r][c] = Integer.parseInt(st.nextToken());
}
}
// 제거된 칸을 채울 숫자들 입력
st = new StringTokenizer(br.readLine());
for (int i = 0; i < m; i++) {
q.offer(Integer.parseInt(st.nextToken()));
}
// k번의 시뮬레이션 실행
for (int i = 0; i < k; i++) {
RotateInfo best = null;
// 모든 가능한 회전 중심점과 각도에 대해 시뮬레이션
for (int r = 1; r <= 3; r++) {
for (int c = 1; c <= 3; c++) {
for (int angle = 1; angle <= 3; angle++) {
RotateInfo candidate = process(r, c, angle);
// 최적의 회전 정보 갱신 (점수가 높은 순, 각도/열/행이 작은 순)
if (best == null || candidate.compareTo(best) < 0) {
best = candidate;
}
}
}
}
int sum = best.score;
if (sum == 0) break; // 제거할 수 있는 그룹이 없으면 종료
// 최적의 회전을 실행하고 연쇄 제거 진행
process(best.row, best.column, best.angle);
while (true) {
fill(); // 빈 칸 채우기
int curScore = bfs(); // 그룹 찾아서 제거
if (curScore == 0) break; // 더 이상 제거할 그룹이 없으면 종료
sum += curScore;
}
sb.append(sum).append(" ");
updateMap(); // 시뮬레이션 결과를 실제 맵에 적용
}
System.out.println(sb.toString());
}
/**
* 임시 맵(copyMap)의 상태를 실제 맵(map)에 복사
*/
static void updateMap() {
for (int r = 0; r < SIZE; r++) {
for (int c = 0; c < SIZE; c++) {
map[r][c] = copyMap[r][c];
}
}
}
/**
* 주어진 위치와 각도로 회전 후 제거 점수를 계산
* @param r 회전 중심점의 행 좌표
* @param c 회전 중심점의 열 좌표
* @param angle 회전 각도 (1: 90도, 2: 180도, 3: 270도)
* @return 회전 정보와 획득 점수를 포함한 RotateInfo 객체
*/
static RotateInfo process(int r, int c, int angle) {
rotate(r, c, angle);
int score = bfs();
return new RotateInfo(score, angle, c, r);
}
/**
* 지정된 중심점을 기준으로 8방향 영역을 회전
* @param r 회전 중심점의 행 좌표
* @param c 회전 중심점의 열 좌표
* @param angle 회전 각도 (1: 90도, 2: 180도, 3: 270도)
*/
static void rotate(int r, int c, int angle) {
// 현재 맵 상태를 임시 맵에 복사
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
copyMap[i][j] = map[i][j];
}
}
// 8방향의 칸들을 angle에 따라 회전
for (int i = 0; i < 8; i++) {
int tnr = r + dr[i];
int tnc = c + dc[i];
// 회전 로직 -> 현재 내 좌표에 와야 하는 요소의 좌표 계산
// 90도 = 중심점을 기준으로 반시계방향 두칸 전의 요소를 가져온다
// 180도 = 중심점을 기준으로 반시계방향 네칸 전의 요소를 가져온다
// 270도 = 중심점을 기준으로 반시계방향 여섯칸 전의 요소를 가져온다
// dr, dc 배열이 이미 반시계방향으로 지정되어 있으므로
// 8칸을 돌면서 angle (1 = 90도, 2 = 180도, 3 = 270도) 에 2를 곱한 값을 현재 i에서 더해주면
// 좌표를 알 수 있다. 이 때 8을 넘어가면 안되기 때문에 모듈러 연산 사용
// 모듈러 연산을 통해서 반복되는 원형 리스트 처리 (중요한 테크닉)
int nr = r + dr[(i + angle * 2) % 8];
int nc = c + dc[(i + angle * 2) % 8];
copyMap[tnr][tnc] = map[nr][nc];
}
}
/**
* BFS로 같은 숫자가 3개 이상 연속된 그룹을 찾아 제거
* @return 제거된 칸의 개수 (점수)
*/
static int bfs() {
// 방문 여부를 체크할 배열
boolean[][] visit = new boolean[SIZE][SIZE];
int score = 0;
for (int y = 0; y < SIZE; y++) {
for (int x = 0; x < SIZE; x++) {
// bfs 진행을 위한 큐 (좌표 저장)
Queue<int[]> queue = new LinkedList<>();
// 같은 값을 발견하면 좌표를 그룹에 넣어주고, 후처리한다. 이 문제의 중요한 테크닉중 하나
List<int[]> group = new ArrayList<>();
if (!visit[y][x]) {
queue.offer(new int[] { y, x });
group.add(new int[] { y, x });
visit[y][x] = true;
}
// BFS로 인접한 같은 숫자 찾기
while (!queue.isEmpty()) {
int[] current = queue.poll();
int r = current[0];
int c = current[1];
for (int i = 0; i < 4; i++) {
int nr = r + dy[i];
int nc = c + dx[i];
// 격자판 범위 체크
if (nr < 0 || nr >= SIZE || nc < 0 || nc >= SIZE) continue;
// 같은 숫자인지 체크
if (copyMap[nr][nc] != copyMap[r][c]) continue;
// 방문 여부 체크
if (visit[nr][nc]) continue;
visit[nr][nc] = true;
queue.add(new int[] { nr, nc });
group.add(new int[] { nr, nc });
}
}
// 그룹 크기가 3 이상이면 제거 처리, 동시에 점수를 계산해서 반환 (제거된 숫자 개수가 점수이므로)
if (group.size() >= 3) {
for (int[] axis : group) {
copyMap[axis[0]][axis[1]] = 0;
score++;
}
}
}
}
return score;
}
/**
* 제거된 칸(0)을 새로운 숫자로 채움
* 왼쪽에서 오른쪽, 아래쪽부터 위로 올라가며 채움
* 채워지는 순서에 맞게 반복문을 적절하게 구성해야함
*/
static void fill() {
for (int c = 0; c < SIZE; c++) {
for (int r = SIZE - 1; r >= 0; r--) {
if (copyMap[r][c] == 0) {
copyMap[r][c] = q.poll();
}
}
}
}
}
/**
* 회전 정보를 저장하고 비교하기 위한 클래스
* 점수가 높은 순, 각도가 작은 순, 열이 작은 순, 행이 작은 순으로 정렬
*/
class RotateInfo implements Comparable<RotateInfo> {
int score; // 획득한 점수
int angle; // 회전 각도
int column; // 회전 중심점의 열 좌표
int row; // 회전 중심점의 행 좌표
public RotateInfo(int score, int angle, int column, int row) {
this.score = score;
this.angle = angle;
this.column = column;
this.row = row;
}
@Override
public int compareTo(RotateInfo o) {
int diff;
// 점수 내림차순
if ((diff = o.score - this.score) != 0) return diff;
// 각도 오름차순
if ((diff = this.angle - o.angle) != 0) return diff;
// 열 좌표 오름차순
if ((diff = this.column - o.column) != 0) return diff;
// 행 좌표 오름차순
return this.row - o.row;
}
}- 삼성 입사문제라는데 2시간안에는 부족했습니다.. 조금 더 디테일 신경쓰면 풀수도 있겠네요
- 위에 풀이는 보조강사님의 풀이입니다
3. 마무리
3.1) WorkShop
- 금일 워크샵은 없습니다
3.2) 더 공부할 것
- BFS
'LG 유플러스 유레카 > 알고리즘' 카테고리의 다른 글
| [20일 차] 알고리즘 (문제 풀기2) (0) | 2025.02.21 |
|---|---|
| [18일 차] 알고리즘 (동적 계획법) (0) | 2025.02.19 |
| [17일 차] 알고리즘 (시뮬레이션) (0) | 2025.02.18 |