문제링크

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

풀이

합이 S라면 1부터 N까지 더하며 S가 넘지 않을때까지 반복한다.

input은 S(1 ≤ S ≤ 4,294,967,295)으로 40억이 넘어가기 때문에 long으로 사용해야 한다.

1부터 더해야 하기 때문에 idx를 1로 시작한다.

200을 예로 들었을 때, 아래의 코드는 sum = 210, idx = 21인 상태에서 if문에 걸리게 된다.

idx++이 된 부분에 대해서 한번 빼주고, sum이 초과되는 부분에서 한번 더 빼준다.

설명으로 하니 복잡한데 반복문 내에 idx와 sum을 찍어보면 아래와 같이 나온다.

//idx sum
1 1
2 3
3 6
...
19 190
20 210
나가!
19

후위연산자로 증가한 값을 하나 줄여주고, 반복문 내에서 sum이 초과한 이전의 숫자를 사용하기 위해 한번 더 빼준다.

따라서 idx를 -2 해주게 되는 것이다.

처음에 이것을 잡는데 시간이 오래 걸렸다.

그 외의 반례로는 input 1, output 1을 확인하기.

코드

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

public class Main{

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long S = Long.parseLong(br.readLine());

        //1부터 계속 더하면서 S가 넘지 않을때까지 반복
        long sum = 0;
        long idx = 1;
        while(true){
        	//System.out.print(idx +" ");
            sum += idx++;
            //System.out.println(sum);
            if(sum > S){
                //System.out.println("나가!");
                idx-=2;
                break;
            }
        }
        System.out.println(idx);
    }
}

그리디는 항상 접근이 어렵고 감을 잡으면 풀이는 쉬워지는 것 같다.

더 많이 풀어봐야지

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

접근 방법

다익스트라를 사용한다.

인접리스트를 사용하여, 겉의 리스트는 출발 도시, 안의 리스트는 연결되는 도시를 넣어준다.

리스트 안의 리스트를 사용할때에는 안의 리스트를 출발도시 수만큼 새로 생성해줘야 한다.

다익스트라 메서드에서 거리 테이블을 만들어준다. 초기는 무한값으로 설정해준다.

다익스트라에서는 메모리와 시간 절약을 위해 우선순위 큐를 사용했다. 가중치가 낮은 순서로 가져오기 때문에 낮은 가중치의 도시 선형탐색과 방문처리를 할 필요가 없어진다.

거리테이블에 있는 값과, 연결된 도시를 거쳐갈때를 비교해서 더 작은 값으로 갱신해준다. 갱신 후 연결노드로 처리하기 위해 큐에 넣어준다.

코드

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

public class Main_1916_최소비용구하기 {

	static int N, M;
	static final int INF = Integer.MAX_VALUE;
	static ArrayList<ArrayList<Node>> list;

	static class Node implements Comparable<Node> {
		int idx, cost; // 연결도시, 가중치

		public Node(int idx, int cost) {
			this.idx = idx;
			this.cost = cost;
		}

		@Override
		public int compareTo(Node o) { // 가중치 오름차순 정렬
			return this.cost - o.cost;
		}

	}

	private static int dijkstra(int start, int end) {
		int[] dist = new int[N + 1]; // 0번째 버림

		// INF 초기화
		for (int i = 0; i < N + 1; i++) {
			dist[i] = INF;
		}

		// 최단거리 테이블 초기 설정 - 최소 거리 순으로 정렬 위해
		PriorityQueue<Node> pq = new PriorityQueue<>();
		pq.add(new Node(start, 0)); // 초기 거리 넣어줌

		// 시작 거리 0
		dist[start] = 0;

		// dijkstra
		while (!pq.isEmpty()) {
			Node cur = pq.poll();

			// 현재 가중치가 더 크다면 진행 안함
			if (dist[cur.idx] < cur.cost)
				continue;

			// 현재 노드와 연결된 노드 파악
			for (int i = 0; i < list.get(cur.idx).size(); i++) {
				Node next = list.get(cur.idx).get(i); // 연결된 노드를 가져옴

				if (dist[next.idx] > cur.cost + next.cost) { // 거쳐가는 것이 더 비용이 작다면
					dist[next.idx] = cur.cost + next.cost;
					pq.offer(new Node(next.idx, dist[next.idx])); // 갱신된 거리를 큐에 넣어준다.
				}
			}
		}

		return dist[end];
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer tokens;

		N = Integer.parseInt(br.readLine()); // 도시의 개수
		M = Integer.parseInt(br.readLine()); // 버스의 개수

		list = new ArrayList<ArrayList<Node>>();

		for (int i = 0; i < N + 1; i++) { // 0번째 노드 버림
			list.add(new ArrayList<>());
		}

		for (int i = 0; i < M; i++) {
			tokens = new StringTokenizer(br.readLine());

			// 출발 도시, 도착 도시, 버스 비용
			int start = Integer.parseInt(tokens.nextToken());
			int end = Integer.parseInt(tokens.nextToken());
			int cost = Integer.parseInt(tokens.nextToken());

			list.get(start).add(new Node(end, cost)); // 연결 도시 저장
		}

		tokens = new StringTokenizer(br.readLine());
		int S = Integer.parseInt(tokens.nextToken()); // 출발 도시
		int E = Integer.parseInt(tokens.nextToken()); // 도착 도시

		System.out.println(dijkstra(S, E));

	}

}

처음에 행렬로 풀었었는데 틀린 답이 나왔다. 백준의 질문 게시판을 살펴보니 인접행렬을 사용했을 경우 중복값에 대한 처리가 어쩌구 써있어서 인접리스트를 사용했다.

기본 등산로 조성은 dfs로 4방향에서 갈 수 있다면 방문처리 해주고 가는 방식으로 짰는데

산을 깎는 경우를 잘 모르겠다.

그냥 N만큼 i,j for문 돌리고 그 안에서 K만큼 반복문 돌려서 다 깎아봤어도 시간 초과가 안 났을 것 같은데 풀다보니 이렇게 풀게 됐다.

정리

❗️현재 높이와 다음 높이를 비교했을 때, 작은 경우와 큰 경우를 따로 생각한다.

❗️큰 경우라면 이전에 깎았는지 확인하고 안깎깎 ? 깎 : 안깎처리를 해준다.

❗️다음 높이가 높을 때 깎는 높이는 현재 높이에서 1만 깎으면 된다. 물론 K만큼 깎았을 때 현재 높이보다 낮아야 한다. 이거 이해하는데 오래 걸렸다

❗️방문처리! 깎은 산! 복원이 중요했다. 갔다 왔으면 원래대로 돌려주자.

❗️제일 높은 봉우리만 시작이 됨.

코드

package SWEA;

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

public class Solution_1949_등산로조성 {

    static int N, K, res;
    static int[][] map;
    static boolean[][] v;
    static int[] dr = {-1, 1, 0, 0}, dc = {0, 0, -1, 1};

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokens;
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());

        for (int tc = 1; tc <= T; tc++) {
            tokens = new StringTokenizer(br.readLine());
            N = Integer.parseInt(tokens.nextToken());
            K = Integer.parseInt(tokens.nextToken());

            map = new int[N][N];
            v = new boolean[N][N];
            int max = 0;

            for (int i = 0; i < N; i++) {
                tokens = new StringTokenizer(br.readLine());
                for (int j = 0; j < N; j++) {
                    map[i][j] = Integer.parseInt(tokens.nextToken());
                    if (max < map[i][j]) max = map[i][j];
                }
            } // end input

            res = 0;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (map[i][j] == max) {
                        dfs(i, j, 1, true);
                    }
                }
            }
            sb.append("#").append(tc).append(" ").append(res).append("\n");
        } // end test case
        System.out.println(sb);
    }

    private static void dfs(int x, int y, int len, boolean flag) {
        v[x][y] = true;
        for (int d = 0; d < 4; d++) {
            int nx = x + dr[d];
            int ny = y + dc[d];

            // 범위 밖, 방문이면 다음 방향
            if (!isRange(nx, ny) || v[nx][ny])
                continue;

            //다음 높이가 현재 높이보다 작을때
            if (map[nx][ny] < map[x][y]) {
                dfs(nx, ny, len + 1, flag);
            } else {//다음 높이가 현재 높이보다 같거나 크고 깎을 수 있을 때
                if (flag && map[nx][ny] - K < map[x][y]) {
                    int temp = map[nx][ny];
                    v[nx][ny] = true;
                    map[nx][ny] = map[x][y]-1;
                    dfs(nx, ny, len + 1, false);
                    map[nx][ny] = temp;
                    v[nx][ny] = false;
                    flag = true;
                }
            }
        }
        v[x][y] = false;
        // 더이상 갈 수 없으면 거리 갱신
        res = Math.max(res, len);
    }

    private static boolean isRange(int x, int y) {
        if (x < 0 || y < 0 || x >= N || y >= N)
            return false;
        return true;
    }
}

접근 방법

배열에 대한 크기를 2칸 더 확장해줬다. 반복문에서 가장 처음에 map[nx][ny]가 블랙홀인지 확인해야 하는데 ArrayIndexOutOfBoundsException 때문에 테두리를 초기에 999로 설정해주었다.

map = new int[N+2][N+2];

//테두리 설정
for(int i=0; i<N+2; i++) {
    map[0][i] = 999;
    map[i][0] = 999;
    map[N+1][i] = 999;
    map[i][N+1] = 999;
}

블록의 경우엔 block에 대한 변경 좌표를 미리 설정해주고 벽일 경우는 5번 블록과 같이 처리했다

static int[][] block = 
	{{},
	{1, 3, 0, 2},
	{3,0,1,2},
	{2,0,3,1},
	{1,2,3,0},
	{1,0,3,2}};

행의 인덱스는 각 블록에 대한 인덱스이고, 열은 순서대로 상하좌우에 대한 처리이다.

웜홀의 경우는 반복문을 탐색해서 짝 웜홀을 찾으면 다음 위치를 짝 웜홀의 위치로 변경해준다

loop:
for(int i=1; i<=N; i++) {
    for(int j=1; j<=N; j++) {
        if(map[i][j] == map[nx][ny]) {
            if(i==nx && j==ny) continue;
            cx = i; cy = j;
            break loop;
        }
    }
}

코드

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

public class Solution {

	static int N, max, sx, sy;
	static int[][] map;
	static int[][] block = {{},
			{1, 3, 0, 2},
			{3,0,1,2},
			{2,0,3,1},
			{1,2,3,0},
			{1,0,3,2}};
			
	static int[] dr = { -1, 1, 0, 0 }, dc = { 0, 0, -1, 1 };

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer tokens;

		int T = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= T; tc++) {
			N = Integer.parseInt(br.readLine());
			map = new int[N+2][N+2];
			
			//테두리 설정
			for(int i=0; i<N+2; i++) {
				map[0][i] = 999;
				map[i][0] = 999;
				map[N+1][i] = 999;
				map[i][N+1] = 999;
			}

			//입력
			for (int i = 1; i <= N; i++) {
				tokens = new StringTokenizer(br.readLine());
				for (int j = 1; j <= N; j++) {
					map[i][j] = Integer.parseInt(tokens.nextToken());
				}
			}
			// -1 블랙홀, 1~5 블록, 6~10 웜홀
			// 모든 0의 위치에 대해 4방향으로 가봄
			max = 0;
			for(int i=1; i<=N; i++) {
				for(int j=1; j<=N; j++) {
					if(map[i][j] == 0) {
						for(int d=0; d<4; d++) {
							sx = i; sy = j;
							move(i, j, d);
						}
					}
				}
			}
			System.out.println("#"+tc+" "+max);

		} // end test case
	}

	private static void move(int cx, int cy, int d) {
		// 점수 >> 벽 || 블록
		int score = 0;

		while (true) {
			// 이동 초기 설정
			int nx = cx + dr[d];
			int ny = cy + dc[d];
			
			// 탈출조건 : 시작위치, 블랙홀
			if ((nx == sx && ny == sy) || map[nx][ny] == -1) {
				max = Math.max(max, score);
				return;
			}
			
			// 벽일 경우
			if (map[nx][ny]==999) { //테두리라면
				// 점수 증가
				score++;
				// 방향 전환
				d = block[5][d];
				// 위치 복원
				cx = nx; cy = ny;
				continue;
			}

			// 0일때 위치 갱신
			if (map[nx][ny] == 0) {
				cx = nx; cy = ny;
				continue; //아래 진행 안함
			}
			
			// 블록일 경우
			else if (1 <= map[nx][ny] && map[nx][ny] <= 5) {
				score++; // 점수 증가
				d = block[map[nx][ny]][d];
				cx = nx; // 위치 갱신
				cy = ny;
			}

			// 웜홀일 경우 다음 위치를 짝 웜홀로 변경
			else if (6 <= map[nx][ny] && map[nx][ny]<= 10) {
				loop:
				for(int i=1; i<=N; i++) {
					for(int j=1; j<=N; j++) {
						if(map[i][j] == map[nx][ny]) {
							if(i==nx && j==ny) continue;
							cx = i; cy = j;
							break loop;
						}
					}
				}
			}
		}
	}
}

풀면서 짜증이 많이 났던 문제였다.

같은 방향으로 연속해서 갈 때 x, y에 대한 설정이 헷갈렸다.

접근 방법

뒤에서부터 최대값을 계산한다.

1 1 3 1 2 와 같은 경우를 예시로 들면 

이렇게 된다.

배열을 뒤에서부터 탐색하면서 최대값을 갱신하고, 최대값보다 작은 경우라면 바로 이익을 계산해준다.

또한, N의 크기가 최대 1,000,000이고 각 날의 매매가는 10,000 이하이기 때문에 1,000,000번 최대 매매가를 더해준다 생각하면 10,000,000,000으로 int 자료형 범위를 넘어서기 때문에 합을 계산하는 변수는 long으로 설정했다.

코드

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

public class Solution_1859_백만장자프로젝트 {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer tokens;
		StringBuilder sb = new StringBuilder();

		int T = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= T; tc++) {
			sb.append("#").append(tc).append(" ");

			int N = Integer.parseInt(br.readLine());
			int[] arr = new int[N];

			int max = 0;
			long profits = 0;

			tokens = new StringTokenizer(br.readLine());
			for (int i = 0; i < N; i++) {
				arr[i] = Integer.parseInt(tokens.nextToken());
			}
			for (int i = N - 1; i >= 0; i--) {
				if(arr[i] > max)
					max = arr[i];
				else
					profits += max - arr[i];
			}
			sb.append(profits).append("\n");
		}
		System.out.println(sb);
	}
}

싸피 코테 치기 전에 풀어봤던 문제인데 다시 풀려니 헷갈려서 더 어렵게 생각했던 것 같다.

수학 들어가면... 🤢

접근 방법

0인 곳을 먼저 클릭해야 한다.

지뢰찾기 게임을 알고 있다면 문제 이해가 쉬워진다.

주어진 예제의 그림을 보면, C를 한번 클릭하면 오른쪽 결과가 나온다.

즉, 주변 지뢰의 수가 0이라면 연속적으로 눌리고, 지뢰의 숫자가 1 이상이면 그 자리에서 멈춘다.

bfs 방식으로 풀이했다.

동작 순서

(1) 맵을 설정한다. 지뢰의 수를 저장할 map 배열과, 방문 체크를 위한 v 배열을 생성한다.

지뢰(*)라면 map에는 -1을, v에는 방문 표시로 1을 체크한다.

(2) 맵에 지뢰의 수를 표시한다. 지뢰가 없는 0인 곳을 클릭하여 8방 탐색 후 지뢰의 개수를 갱신한다.

(3) 0인 곳을 먼저 누른다. 주변에 지뢰가 없는 곳이어야 하고, 방문하지 않은 곳이어야 한다.

(3-1) bfs로 8방 탐색을 한다. 0이면 큐에 넣어주고 나머지 1 이상의 숫자에 대해서는 방문처리만 해준다.

(4) 방문하지 않은 나머지를 눌러준다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;

public class Solution_1868_파핑파핑지뢰찾기 {

	static int N, res;
	static int[][] map;
	static int[][] v;

	static int[] dr = { -1, 1, 0, 0, -1, -1, 1, 1 };
	static int[] dc = { 0, 0, -1, 1, -1, 1, -1, 1 };

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		

		for (int tc = 1; tc <= T; tc++) {
			N = Integer.parseInt(br.readLine());
			map = new int[N][N]; // 지뢰와 지뢰 수 표시 맵
			v = new int[N][N]; // 클릭한거 체크용
			res = 0;

			String str;
			for (int i = 0; i < N; i++) {
				str = br.readLine();
				for (int j = 0; j < N; j++) {
					if (str.charAt(j) == '*') {
						map[i][j] = -1; // 지뢰면 -1로 표시
						v[i][j] = 1; // 지뢰 있는 곳 방문처리
					}
				}
			} // end input

			// 맵에 지뢰 수 표시. 지뢰:-1 나머지:지뢰수
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (map[i][j] == 0) {
						// i,j위치에서 8방 지뢰 수 세기
						int cnt = 0;
						for (int d = 0; d < 8; d++) {
							int nx = i + dr[d];
							int ny = j + dc[d];

							if (!isRange(nx, ny))
								continue;
							if (map[nx][ny] != -1)
								continue;
							cnt++;
						}
						map[i][j] = cnt; // 지뢰 수 맵에 갱신
					}
				}
			}

			// 8방이 0인 곳만 누르기
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (map[i][j] == 0 && v[i][j] == 0) { // 주변에 지뢰가 없고, 방문 x
						click(i, j);
						res++; // 클릭
					}
				}
			}

			// 남은 0인 부분 누르기
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (v[i][j] == 0) {
						res++;
					}
				}
			}
			sb.append("#").append(tc).append(" ").append(res).append("\n");
		} // end test case
		System.out.println(sb);
	}

	private static void click(int x, int y) {
		// 8방 탐색 해서 0이라면 큐에, 지뢰가 아니고 숫자라면 방문체크만
		Queue<int[]> q = new ArrayDeque<>();
		q.offer(new int[] { x, y });
		v[x][y] = 1;// 방문체크

		while (!q.isEmpty()) {
			int[] cur = q.poll();

			for (int d = 0; d < 8; d++) {
				int nx = cur[0] + dr[d];
				int ny = cur[1] + dc[d];

				// 범위확인
				if (!isRange(nx, ny))
					continue;
				// 지뢰라면 건너뜀
				if (map[nx][ny] == -1)
					continue;
				// 이미 클릭했다면 건너뜀
				if (v[nx][ny] == 1)
					continue;
				// 0이라면 큐에 넣음
				if (map[nx][ny] == 0) {
					q.offer(new int[] { nx, ny });
				}
				// 지뢰수가 표시된 위치 방문처리
				v[nx][ny] = 1;
			}
		}
	}

	private static boolean isRange(int nx, int ny) {
		if (nx >= 0 && ny >= 0 && nx < N && ny < N)
			return true;
		return false;
	}

}

즐겨하는 게임이 지뢰찾기이면서도 0이 연속적으로 눌리는 경우에 대해서 이해하지 못했다.

지뢰찾기 왜 했지?

[ 동작 순서 ]

1. 맵 확장
   • 배열 생성
   • 자물쇠 위치
2. 열쇠 위치 → 모든 위치 확인
   • 확장맵과 열쇠를 더해줌
   • 자물쇠 범위 확인
     • true → return true
     • false → 열쇠 회전
3. 반복문 종료시 return false → 열쇠와 자물쇠가 맞지 않음

맵 확장

- 배열 생성

자물쇠는 N의 크기를 가지고 있다. 열쇠가 배열의 범위를 벗어나 확인이 가능하기 때문에 맵을 N + (M*2) - 2 만큼 확장해 준다.

자물쇠의 크기 + 열쇠 2개 - 겹치는 부분

- 배열 중심에 자물쇠 위치 시키기

맵의 중심에 자물쇠를 위치시킨다. 확장된 맵에서의 자물쇠의 위치는 열쇠길이-1 부터 시작위치에서 자물쇠의 길이만큼 더해준 값이다.

자물쇠를 확장맵에 위치시키고 나면 다음과 같이 맵이 나타난다.

열쇠 위치

2중 반복문을 사용한다. 인덱스의 범위는 (0,0) 부터 자물쇠의 마지막 위치인 (열쇠의 길이+자물쇠의 길이)-1 만큼이다.

확장맵 + 열쇠

확장된 맵에 현재 열쇠의 인덱스 (i, j) 부터 열쇠의 크기까지 맵에 더한다

이 결과로 맵에 저장되는 값은 0, 1, 2인데 문제에서 구하고자 하는 값은 1이 된다.

0 : 열쇠와 자물쇠의 홈끼리 만난 경우

1 : 열쇠의 돌기와 자물쇠의 홈이 만난 경우 → 정상

2 : 열쇠의 돌기와 자물쇠의 돌기가 만난 경우

자물쇠가 열리는지 확인

전체 맵을 확인 할 필요 없이 자물쇠가 있는 위치만 확인한다. 이 문제의 답은 자물쇠의 홈이 모두 채워지는 경우여야 하기 때문이다.

자물쇠의 범위는 (열쇠의 길이 - 1) ~ (열쇠의 길이 + 자물쇠의 길이 - 1) 이 된다.

해당 범위를 확인하는 check 메서드를 만들어 범위가 전부 1인지 확인한다. check 메서드가 true를 반환한다면 현재 열쇠는 맞는 열쇠가 되기 때문에 true를 return 하고 종료한다. false를 반환한다면 현재 열쇠가 맞지 않기 때문에 방향을 바꿔준다.

방향을 모두 바꿔도 맞지 않는다면 다음 위치로 넘어간다.

열쇠 회전

한번에 90도씩 회전시킨다. 90도를 회전시키면 배열의 크기가 3인 인덱스의 매칭은 다음과 같다.

[행][열]

rotate[0][0] = origin[2][0]

rotate[0][1] = origin[1][0]

rotate[0][2] = origin[0][0]

rotate[1][0] = origin[2][1]

rotate[1][1] = origin[1][1]

rotate[1][2] = origin[0][1]

rotate[2][0] = origin[2][2]

rotate[2][1] = origin[1][2]

rotate[2][2] = origin[0][2]

행과 열을 읽을 때 행을 아래에서부터 위로 읽은 것을 열에 저장한다. 복잡하게 설명하지만 직접 써보면서 풀면 이해가 쉬워진다.

전체 코드

public class Solution_자물쇠와열쇠 {

    static int M, N;

    public static boolean solution(int[][] key, int[][] lock) {
        N = lock.length; //자물쇠의 크기
        M = key.length; //열쇠의 크기

        //맵을 자물쇠의 크기에서 열쇠의 크기만큼 확장해줌
        int[][] map = new int[N + (M * 2) - 2][N + (M * 2) - 2];

        //중심에 자물쇠 위치시키기. i/j -> map에 대한 인덱스. k/l -> 자물쇠에 대한 인덱스
        for (int i = M - 1, k = 0; i < M - 1 + N; i++, k++) {
            for (int j = M - 1, l = 0; j < M - 1 + N; j++, l++) {
                map[i][j] = lock[k][l];
            }
        }

        //임시 복사 배열
        int[][] copyMap = new int[map.length][map.length];

        //0,0부터 N-1+M까지 열쇠 두기
        for (int i = 0; i < M + N - 1; i++) {
            for (int j = 0; j < M + N - 1; j++) {
                for (int d = 0; d < 4; d++) {
                    //맵 복사
                    MapCopy(copyMap, map);

                    //열쇠를 복사맵에 더함
                    for (int k = 0; k < M; k++) {
                        for (int l = 0; l < M; l++) {
                            copyMap[i + k][j + l] += key[k][l];
                        }
                    }

                    //자물쇠가 열리는지 확인
                    if (check(copyMap)) { //맞는다면 트루
                        return true;
                    }

                    //방향이 아니라면 돌려줌
                    key = rotate(key);
                }
            }//end j
        }//end i for check all index

        return false;
    }

    private static void MapCopy(int[][] copyMap, int[][] map) {
        //맵 복사함
        for (int k = 0; k < map.length; k++) {
            System.arraycopy(map[k], 0, copyMap[k], 0, map[k].length);
        }
    }

    private static int[][] rotate(int[][] key) {
        int[][] copyKey = new int[M][M];
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < M; j++) {
                copyKey[i][j] = key[M - 1 - j][i];
            }
        }
        return copyKey;
    }

    private static boolean check(int[][] copyMap) {
        //자물쇠 영역이 전체가 1인지 확인함
        for (int k = M - 1; k < M - 1 + N; k++) {
            for (int l = M - 1; l < M - 1 + N; l++) {
                if (copyMap[k][l] != 1) { //1이 아닌 값이 들어갔다면 돌기끼리 만났거나 홈이 안채워짐
                    return false;
                }
            }
        }
        return true;
    }
}

문제 링크

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

코드

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

public class Main {

	static int N, M;
	static char[][] map;

	static class Pos {
		int x, y, cnt, key;

		public Pos(int x, int y, int cnt, int key) {
			this.x = x;
			this.y = y;
			this.cnt = cnt;
			this.key = key;
		}	
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer tokens = new StringTokenizer(br.readLine());
		N = Integer.parseInt(tokens.nextToken());
		M = Integer.parseInt(tokens.nextToken());
		map = new char[N][M];

		int startX = 0, startY = 0;
		String temp;
		for (int i = 0; i < N; i++) {
			temp = br.readLine();
			for (int j = 0; j < M; j++) {
				map[i][j] = temp.charAt(j);
				if (map[i][j] == '0') {
					startX = i; // 시작 위치 설정
					startY = j;
				}
			}
		} // end input

		bfs(startX, startY);

	}

	static int[] dr = { -1, 1, 0, 0 };
	static int[] dc = { 0, 0, -1, 1 };

	private static void bfs(int startX, int startY) {
		Queue<Pos> q = new ArrayDeque<>();
		boolean[][][] v = new boolean[64][N][M]; // a~f까지 키 주웠는지 확인 배열
		q.add(new Pos(startX, startY, 0, 0)); // 첫번째 출발 위치 넣음. 키는 아무것도 없음
		map[startX][startY] = '.';

		while (!q.isEmpty()) {
			Pos cur = q.poll();

			for (int d = 0; d < 4; d++) {
				int nx = cur.x + dr[d];
				int ny = cur.y + dc[d];

				if (!isRange(nx, ny) || map[nx][ny] == '#' || v[cur.key][nx][ny])
					continue; // 범위 벗어나거나, 벽이거나, 현재키로 방문했으면 다른방향
				
				if(map[nx][ny]=='1') {
					System.out.println(cur.cnt+1);
					return;
				}
				
				if (map[nx][ny] == '.') { // 갈 수 있으면 다음 방향 넣음
					v[cur.key][nx][ny] = true;
					q.add(new Pos(nx, ny, cur.cnt+1, cur.key));
				}
				if (map[nx][ny] >= 'a' && map[nx][ny] <= 'f') {// 소문자라면
					int gainKey = 1 << (map[nx][ny] - 'a');
					gainKey = cur.key | gainKey; // or 연산으로 현재 얻은 키 갱신

					if (!v[cur.key][nx][ny]) { //현재 키들로 방문하지 않았을 때 방문처리해줌 ->다시 갈 필요 없기 때문
						v[cur.key][nx][ny] = true;
						v[gainKey][nx][ny] = true;
						q.add(new Pos(nx, ny, cur.cnt + 1, gainKey));
					}
				}
				if (map[nx][ny] >= 'A' && map[nx][ny] <= 'F') {
					int checkKey = 1 << (map[nx][ny]-'A');
					if((cur.key & checkKey) > 0) { //키와 문의 대응이 1이상 존재한다면
						v[cur.key][nx][ny] = true;
						q.add(new Pos(nx, ny, cur.cnt+1, cur.key));
					}
				}

			}
		}
		System.out.println(-1);
		return;
	}

	private static boolean isRange(int x, int y) {
		if (x < 0 || y < 0 || x >= N || y >= M)
			return false;
		return true;
	}
}

bfs로 풀었는데 비트마스킹으로도 풀 수 있다!

접근 방법

main

1. 가장 처음에 세로 방향에 대해서 성능 검사를 통과할 수 있는지 확인한다. isTest()
2. 통과하지 못한다면 dfs() 실행

dfs()

• 약품을 투입하지 않는 경우, 약품을 투입하는 경우(A/B)로 나누어 모든 열에 대해 진행한다.
• 마지막 열에 도착했으면 isTest()로 성능 검사를 한다.
• 성능 검사에 통과했다면 약품 최소 투여 횟수를 갱신한다.
• 백트래킹으로 현재 파라미터의 약품 주입 횟수가 갱신된 최소 횟수를 넘었다면 더이상 탐색하지 않는다.

isTest()

• 가장 바깥의 반복문은 모든 열에 대해서 반복한다.
• 검사 통과를 위한 boolean 변수를 선언한다.
• 첫번째 값을 prev 변수에 저장한다
• 모든 행에 대한 반복문 시작
• 이전과 같다면 cnt 증가, 아니라면 cnt를 1로 돌려주고 이전값을 현재 값으로 갱신한다.
• 행을 탐색하면서 cnt가 K에 도달했다면 이 열은 성능검사에서 통과. 다음 열로 진행
• 하나의 열에 대해 모든 행 탐색이 끝났는데 false라면 그 열은 성능검사 통과 못함

import java.util.Scanner;

public class Solution {

	static int D, W, K, res;
	static int[][] map, copy;
	static boolean[] check;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			res = Integer.MAX_VALUE; // 약품 투입 최소 횟수

			D = sc.nextInt();
			W = sc.nextInt();
			K = sc.nextInt();

			// 0==A, 1==B
			map = new int[D][W];
			copy = new int[D][W];
			for (int i = 0; i < D; i++) {
				for (int j = 0; j < W; j++) {
					map[i][j] = copy[i][j] = sc.nextInt();
				}
			} // end input

			if (isTest()) {
				res = 0;
			} else {
				dfs(0, 0);
			}

			System.out.println("#" + tc + " " + res);
		}
		sc.close();
	}

	private static void dfs(int idx, int cnt) { // 검사 행, 용액 주입 횟수
		// 백트래킹
		if (cnt >= res)
			return;

		// 끝 행까지 dfs를 탔다면 반환
		if (idx == D) {
			// 모든 열이 K를 만족한다면 최소값 갱신
			if (isTest()) {
				res = Math.min(res, cnt);
			}
			return;
		}

		// 한 열에 대해서 idx를 행까지 검사

		// 지금 행을 안 바꾸는 경우
		dfs(idx + 1, cnt);

		// 현재 행을 A로 바꾸는 경우
		for (int j = 0; j < W; j++) {
			copy[idx][j] = 0;
		}
		dfs(idx + 1, cnt + 1);

		// 현재 행을 B로 바꾸는 경우
		for (int j = 0; j < W; j++) {
			copy[idx][j] = 1;
		}
		dfs(idx + 1, cnt + 1);

		// 원래대로 돌려줌
		for (int j = 0; j < W; j++) {
			copy[idx][j] = map[idx][j];
		}

	}

	private static boolean isTest() {
		for (int j = 0; j < W; j++) {
			boolean flag = false;
			int cnt = 1;
			int prev = copy[0][j];
			for (int i = 1; i < D; i++) {
				if (prev == copy[i][j]) {
					cnt++;
				} else {
					cnt = 1;
					prev = copy[i][j];
				}

				if (cnt == K) {
					flag = true;
					break; // 해당 열이 검사에서 통과함
				}
			}
			if (!flag)
				return false; // 한 열이라도 검사에서 통과하지 못하면 false 반환
		}
		return true; // 전부 탐색했을 때 통과된 상태
	}

}

스터디와 역량테스트 때문에 여러번 풀었던 문제였는데 풀때마다 풀이가 조금씩 달라지는 문제였다.

성능검사를 할 때 진행 중 성능검사에 통과하여 다음 열로 진행하는 경우와, 모든 행을 탐색하고 나서 이 행이 통과되는지를 확인하는 부분에서 디버깅이 오래 걸렸다.

또한, 용액을 주입할 때 다른 사람의 코드를 보며 깔끔하게 짜는 코드를 몇가지 확인했다.

• A, B에 대한 값을 final int로 선언하여 직관적으로 변수 관리하기
• 행의 크기만큼 배열 2개를 A, B값으로 전부 변경해두고 arr[idx] = A[idx]와 같이 관리하기

두번째 방법을 보고 나도 저렇게 짤걸!!! 소리없는 절규를 했다. W만큼 반복문을 돌릴 필요가 없을 뿐더러, 배열 값 임시저장해두고 dfs 다 돌았을때 = 연산자로 복귀만 시켜주면 되는 방법... 코드를 짜는 방법에 대해서도 다시 생각해보게 되었다.

문제 링크

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

접근 방법

1. 맵을 입력 받을 때 전체 인구수를 구한다
2. 경계선을 구한다
3. fifth배열에 경계선을 true로 표시한다.
4. 1~4 선거구 범위에 맞춰 popu 배열에 각 선거구의 인구수를 저장한다
5. 5번 선거구 = 전체 인구수 - popu배열 전체 합
6. popu 배열을 정렬해서 최대값과 최소값의 차이를 구해 전체 인구 차이의 최소값을 갱신한다.

1. 맵을 입력 받을 때 전체 인구수를 구한다

totalPopu = 0; //전체 인구수를 저장하기 위한 변수

map = new int[N + 1][N + 1];

for (int i = 1; i <= N; i++) {
	StringTokenizer tokens = new StringTokenizer(br.readLine());
	for (int j = 1; j <= N; j++) {
		map[i][j] = Integer.parseInt(tokens.nextToken());
		totalPopu += map[i][j]; //총 인구수를 구함
	}
}

경계선을 정하고 선거구 범위에 맞춰 인구수를 구한다면, 5번 선거구의 인구는 전체인구 - 1~4번 선거구 인구로 계산할 수 있다.

2. 경계선을 구한다.

• 기준점 (x, y)
• 경계의 길이 d1, d2

배열의 전체를 돌 x, y와 경계의 길이가 될 d1과 d2를 구한다. 4중 for문을 사용한다.

for (int x = 1; x <= N; x++) {
    for (int y = 1; y <= N; y++) {
        for (int d1 = 1; d1 <= N; d1++) {
            for (int d2 = 1; d2 <= N; d2++) {
				//3~6번 실행
            }
        }
    }
}//end 4 for

3. fifth 배열에 경계선을 true로 표시한다

문제에 주어진 경계선 조건은 다음과 같다

1. (x, y), (x+1, y-1), ..., (x+d1, y-d1)
2. (x, y), (x+1, y+1), ..., (x+d2, y+d2)
3. (x+d1, y-d1), (x+d1+1, y-d1+1), ... (x+d1+d2, y-d1+d2)
4. (x+d2, y+d2), (x+d2+1, y+d2-1), ..., (x+d2+d1, y+d2-d1)

이 경계선을 그대로 반복문에 적용한다.

for (int x = 1; x <= N; x++) {
    for (int y = 1; y <= N; y++) {
        for (int d1 = 1; d1 <= N; d1++) {
            for (int d2 = 1; d2 <= N; d2++) {

				//문제에 주어진 x, y, d1, d2의 조건
                //(d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N)
                if (x + d1 + d2 > N) continue;
                if (y - d1 < 1 || y + d2 > N) continue;

                popu = new int[5]; //1~5번 선거구의 인구수를 저장할 배열

                //5번 선거구의 경계선을 지역구 배열에 true 표시
                //각 지역구별로 다르게 범위를 구하면서 인구수 저장
                boolean[][] fifth = new boolean[N + 1][N + 1];
                //경계선 긋기
                for (int r = x, c = y; r <= x + d1; r++, c--)
                    fifth[r][c] = true;
                for (int r = x, c = y; r <= x + d2; r++, c++)
                    fifth[r][c] = true;
                for (int r = x + d1, c = y - d1; r <= x + d1 + d2; r++, c++)
                    fifth[r][c] = true;
                for (int r = x + d2, c = y + d2; r <= x + d2 + d1; r++, c--)
                    fifth[r][c] = true;

            }
        }
    }
}//end 4 for

위의 코드를 실행하면 다음과 같은 배열이 만들어지고, true가 5번 선거구의 경계선이 된다.

처음에 r, c를 2중 for문을 사용했더니 □ 모양의 경계선이 만들어졌다. r과 c를 동시에 증감시켜야 ◇ 모양으로 경계선이 생성된다.

4. 1~4 선거구 범위에 맞춰 popu 배열에 각 선거구의 인구수를 저장한다

선거구 범위

• 1번 선거구: 1 ≤ r < x+d1, 1 ≤ c ≤ y
• 2번 선거구: 1 ≤ r ≤ x+d2, y < c ≤ N
• 3번 선거구: x+d1 ≤ r ≤ N, 1 ≤ c < y-d1+d2
• 4번 선거구: x+d2 < r ≤ N, y-d1+d2 ≤ c ≤ N

한 행씩 읽으면서 1~4구역을 선거구 범위에 맞춰 읽는다. 한 행을 읽는 도중 경계선을 만난다면 다음 행으로 넘어간다.

1번과 3번 구역은 좌->우로 읽으면 되지만 2번과 4번 구역은 화살표와 같이 열의 끝에서 앞으로 읽어야 경계선을 만날 수 있다.

//1번 선거구 인원수 더하기
for (int r = 1; r < x + d1; r++) {
    for (int c = 1; c <= y; c++) {
        if (fifth[r][c]) break; //경계선 만나면 다음줄로
        popu[0] += map[r][c];
    }
}

//2번 선거구
for (int r = 1; r <= x + d2; r++) {
    for (int c = N; c >= y + 1; c--) {//열을 뒤에서부터 읽음
        if (fifth[r][c]) break;
        popu[1] += map[r][c];
    }
}

//3번 선거구
for (int r = x + d1; r <= N; r++) {
    for (int c = 1; c < y - d1 + d2; c++) {
        if (fifth[r][c]) break;
        popu[2] += map[r][c];
    }
}

//4번 선거구
for (int r = x + d2 + 1; r <= N; r++) {
    for (int c = N; c >= y - d1 + d2; c--) {//열을 뒤에서부터 읽음
        if (fifth[r][c]) break;
        popu[3] += map[r][c];
    }
}

5. 5번 선거구 = 전체 인구수 - popu배열 전체 합

//5번 선거구 인원수 구하기
int tempSum = 0;
for (int k = 0; k < 4; k++) {
    tempSum += popu[k];
}
popu[4] = totalPopu - tempSum;

6. popu 배열을 정렬해서 최대값과 최소값의 차이를 구해 전체 인구 차이의 최소값을 갱신한다

Arrays.sort(popu);

minPopu = Math.min(minPopu, (popu[4] - popu[0])); //최대-최소 인구수 가장 작은 값 갱신

전체 코드

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

public class Main_17779_게리맨더링2 {
    static int N, totalPopu;
    static int[] popu; //인구수를 저장할 배열
    static int[][] map;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        totalPopu = 0;
        map = new int[N + 1][N + 1];
        for (int i = 1; i <= N; i++) {
            StringTokenizer tokens = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                map[i][j] = Integer.parseInt(tokens.nextToken());
                totalPopu += map[i][j]; //총 인구수를 구함
            }
        }//end input

        //(x, y) (dx, dy)를 정한다
        //정한 조건에 따라 경계선을 표시한다
        //1~4번 선거구를 구하고 popu 배열에 순서대로 넣는다
        //5번 선거구이면 총인구수 - popu합을 빼서 5번 선거구 인구수로 넣어준다
        //배열 정렬하고 (맨 뒤 - 맨 앞)을 구해서 최소값 갱신

        int minPopu = Integer.MAX_VALUE;

        for (int x = 1; x <= N; x++) {
            for (int y = 1; y <= N; y++) {
                for (int d1 = 1; d1 <= N; d1++) {
                    for (int d2 = 1; d2 <= N; d2++) {

                        //1. 의 d1, d2에 대한 길이 조건에 해당되지 않으면 탐색 안 함
                        if (x + d1 + d2 > N) continue;
                        if (y - d1 < 1 || y + d2 > N) continue;

                        popu = new int[5];

                        //5번 선거구의 경계선을 지역구 배열에 true 표시
                        //각 지역구별로 다르게 범위를 구하면서 인구수 저장
                        boolean[][] fifth = new boolean[N + 1][N + 1];
                        //경계선 긋기
                        for (int r = x, c = y; r <= x + d1; r++, c--)
                            fifth[r][c] = true;
                        for (int r = x, c = y; r <= x + d2; r++, c++)
                            fifth[r][c] = true;
                        for (int r = x + d1, c = y - d1; r <= x + d1 + d2; r++, c++)
                            fifth[r][c] = true;
                        for (int r = x + d2, c = y + d2; r <= x + d2 + d1; r++, c--)
                            fifth[r][c] = true;

                        //한줄씩 범위대로 탐색
                        //1번 선거구 인원수 더하기
                        for (int r = 1; r < x + d1; r++) {
                            for (int c = 1; c <= y; c++) {
                                if (fifth[r][c]) break; //경계선 만나면 다음줄로
                                popu[0] += map[r][c];
                            }
                        }

                        //2번 선거구
                        for (int r = 1; r <= x + d2; r++) {
                            for (int c = N; c >= y + 1; c--) {//열을 뒤에서부터 읽음
                                if (fifth[r][c]) break;
                                popu[1] += map[r][c];
                            }
                        }

                        //3번 선거구
                        for (int r = x + d1; r <= N; r++) {
                            for (int c = 1; c < y - d1 + d2; c++) {
                                if (fifth[r][c]) break;
                                popu[2] += map[r][c];
                            }
                        }

                        //4번 선거구
                        for (int r = x + d2 + 1; r <= N; r++) {
                            for (int c = N; c >= y - d1 + d2; c--) {//열을 뒤에서부터 읽음
                                if (fifth[r][c]) break;
                                popu[3] += map[r][c];
                            }
                        }

                        //인구수가 0인 곳이 있으면 계산 안하고 넘어감
                        if (popu[0] == 0 || popu[1] == 0 || popu[2] == 0 || popu[3] == 0) {
                            break;
                        }

                        //5번 선거구 인원수 구하기
                        int tempSum = 0;
                        for (int k = 0; k < 4; k++) {
                            tempSum += popu[k];
                        }
                        popu[4] = totalPopu - tempSum;

                        Arrays.sort(popu);

                        minPopu = Math.min(minPopu, (popu[4] - popu[0])); //최대-최소 인구수 가장 작은 값 갱신

                    }
                }
            }
        }//end 4 for

        System.out.println(minPopu);

    }//end main
}

풀고 나니 어려운 문제가 아니었으나, 문제를 이해하는데 시간이 오래 걸렸다.

조건에 나온대로 for문의 범위를 정하면 금방 풀 수 있는 문제였다. 난 금방 못 풀었지만.