[구름, 백준/완전탐색] 동전 퍼즐

문제

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

https://level.goorm.io/exam/195037/%EB%8F%99%EC%A0%84-%ED%8D%BC%EC%A6%90/quiz/1

구름LEVEL

 

해결 방법

이번 문제는 1번 동전 배치 위에 2번 동전 배치를 한 칸씩 이동시켜 동전이 가장 많이 겹치는 경우를 찾으면 되는 문제이다. 유사한 개념으로 CNN에서 Kernel의 stride를 1로 했을때와 비슷하다고 생각할 수 있다.

 

출처: https://post-blog.insilicogen.com/blog/346

구현에서 고려해야할 점은 가로, 세로 각각 더 긴 길이만큼 이동시켜야한다. 가로 세로 각각 더 긴 길이만큼 탐색해야하는 이유는, 모든 경우를 탐색하기 위함이다. 짧은 길이로 탐색하게되면 도달하지 않고 넘어가게 되는 경우가 생기기 때문이다.

주요 로직

1. 1번 동전 배치와 2번 동전 배치의 가로 세로를 각각 비교하여 최대값을 찾음
2. 음의 세로 길이 ~ 양의 세로 길이, 음의 가로 길이 ~ 양의 가로 길이까지 2중 반복문으로 반복하여 동전 배치를 이동시키는 모든 경우의 수 탐색
3. 1번 동전 배치를 순회하며 2번 동전 배치를 이동시켰을때 겹치는 경우의 수 합산

소스코드

import java.io.*;
class Main {
	static int H1, W1;
	static int H2, W2;
	static String[][] map1;
	static String[][] map2;
	static int coinCnt = 0;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] line1 = br.readLine().split(" ");
		H1 = Integer.parseInt(line1[0]);
		W1 = Integer.parseInt(line1[1]);
		map1 = new String[H1][W1];
		for(int i = 0; i < H1; i++){
			String[] l = br.readLine().split("");
			for(int j = 0; j < W1; j++){
				map1[i][j] = l[j];
				if(map1[i][j].equals("O"))
					coinCnt++;
			}
		}
		
		String[] line2 = br.readLine().split(" ");
		H2 = Integer.parseInt(line2[0]);
		W2 = Integer.parseInt(line2[1]);
		map2 = new String[H2][W2];
		for(int i = 0; i < H2; i++){
			String[] l = br.readLine().split("");
			for(int j = 0; j < W2; j++){
				map2[i][j] = l[j];
			}
		}

		int maxCnt = 0;
		int compH = Math.max(H1, H2);
		int compW = Math.max(W1, W2);
		for(int i = compH * -1; i <= compH; i++){
			for(int j = compW * -1; j <= compW; j++){
				int cnt = check(j, i);
				if(cnt > maxCnt)
					maxCnt = cnt;
			}
		}


		System.out.println(coinCnt - maxCnt);
	}

	static int check(int diffX, int diffY){
		int cnt = 0;
		for (int i = 0; i < H1; i++){
			for(int j = 0; j < W1; j++){
				int newX = j + diffX;
				int newY = i + diffY;
				if(newX < 0 || newX >= W2 || newY < 0 || newY >= H2)
					continue;
				if(map1[i][j].equals("O") && map2[newY][newX].equals("O"))
					cnt++;
			}
		}

		return cnt;
	}
}