[2018 KAKAO BLIND RECRUITMENT] ํ”„๋ Œ์ฆˆ4๋ธ”๋ก

๋ฌธ์ œ

๋ฌธ์ œ ์„ค๋ช…

๋ธ”๋ผ์ธ๋“œ ๊ณต์ฑ„๋ฅผ ํ†ต๊ณผํ•œ ์‹ ์ž… ์‚ฌ์› ๋ผ์ด์–ธ์€ ์‹ ๊ทœ ๊ฒŒ์ž„ ๊ฐœ๋ฐœ ์—…๋ฌด๋ฅผ ๋งก๊ฒŒ ๋˜์—ˆ๋‹ค. ์ด๋ฒˆ์— ์ถœ์‹œํ•  ๊ฒŒ์ž„ ์ œ๋ชฉ์€ โ€œํ”„๋ Œ์ฆˆ4๋ธ”๋กโ€. ๊ฐ™์€ ๋ชจ์–‘์˜ ์นด์นด์˜คํ”„๋ Œ์ฆˆ ๋ธ”๋ก์ด 2ร—2 ํ˜•ํƒœ๋กœ 4๊ฐœ๊ฐ€ ๋ถ™์–ด์žˆ์„ ๊ฒฝ์šฐ ์‚ฌ๋ผ์ง€๋ฉด์„œ ์ ์ˆ˜๋ฅผ ์–ป๋Š” ๊ฒŒ์ž„์ด๋‹ค.

โœ… ์˜ˆ์‹œ ์ผ€์ด์Šค ์„ค๋ช…

๊ทธ๋ฆผ

๋งŒ์•ฝ ํŒ์ด ์œ„์™€ ๊ฐ™์ด ์ฃผ์–ด์งˆ ๊ฒฝ์šฐ, ๋ผ์ด์–ธ์ด 2ร—2๋กœ ๋ฐฐ์น˜๋œ 7๊ฐœ ๋ธ”๋ก๊ณผ ์ฝ˜์ด 2ร—2๋กœ ๋ฐฐ์น˜๋œ 4๊ฐœ ๋ธ”๋ก์ด ์ง€์›Œ์ง„๋‹ค. ๊ฐ™์€ ๋ธ”๋ก์€ ์—ฌ๋Ÿฌ 2ร—2์— ํฌํ•จ๋  ์ˆ˜ ์žˆ์œผ๋ฉฐ, ์ง€์›Œ์ง€๋Š” ์กฐ๊ฑด์— ๋งŒ์กฑํ•˜๋Š” 2ร—2 ๋ชจ์–‘์ด ์—ฌ๋Ÿฌ ๊ฐœ ์žˆ๋‹ค๋ฉด ํ•œ๊บผ๋ฒˆ์— ์ง€์›Œ์ง„๋‹ค.

๊ทธ๋ฆผ

๋ธ”๋ก์ด ์ง€์›Œ์ง„ ํ›„์— ์œ„์— ์žˆ๋Š” ๋ธ”๋ก์ด ์•„๋ž˜๋กœ ๋–จ์–ด์ ธ ๋นˆ ๊ณต๊ฐ„์„ ์ฑ„์šฐ๊ฒŒ ๋œ๋‹ค.

๊ทธ๋ฆผ

๋งŒ์•ฝ ๋นˆ ๊ณต๊ฐ„์„ ์ฑ„์šด ํ›„์— ๋‹ค์‹œ 2ร—2 ํ˜•ํƒœ๋กœ ๊ฐ™์€ ๋ชจ์–‘์˜ ๋ธ”๋ก์ด ๋ชจ์ด๋ฉด ๋‹ค์‹œ ์ง€์›Œ์ง€๊ณ  ๋–จ์–ด์ง€๊ณ ๋ฅผ ๋ฐ˜๋ณตํ•˜๊ฒŒ ๋œ๋‹ค.

๊ทธ๋ฆผ

์ž…๋ ฅ์œผ๋กœ ๋ธ”๋ก์˜ ์ฒซ ๋ฐฐ์น˜๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ์ง€์›Œ์ง€๋Š” ๋ธ”๋ก์€ ๋ชจ๋‘ ๋ช‡ ๊ฐœ์ธ์ง€ ํŒ๋‹จํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ œ์ž‘ํ•˜๋ผ.

์ž…๋ ฅ ํ˜•์‹

  • ์ž…๋ ฅ์œผ๋กœ ํŒ์˜ ๋†’์ด m, ํญ n๊ณผ ํŒ์˜ ๋ฐฐ์น˜ ์ •๋ณด board๊ฐ€ ๋“ค์–ด์˜จ๋‹ค.
  • 2 <= n, m <= 30
  • board๋Š” ๊ธธ์ด n์ธ ๋ฌธ์ž์—ด m๊ฐœ์˜ ๋ฐฐ์—ด๋กœ ์ฃผ์–ด์ง„๋‹ค. ๋ธ”๋ก์„ ๋‚˜ํƒ€๋‚ด๋Š” ๋ฌธ์ž๋Š” ๋Œ€๋ฌธ์ž A์—์„œ Z๊ฐ€ ์‚ฌ์šฉ๋œ๋‹ค.

์ถœ๋ ฅ ํ˜•์‹

์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์ง„ ํŒ ์ •๋ณด๋ฅผ ๊ฐ€์ง€๊ณ  ๋ช‡ ๊ฐœ์˜ ๋ธ”๋ก์ด ์ง€์›Œ์งˆ์ง€ ์ถœ๋ ฅํ•˜๋ผ.

์ž…์ถœ๋ ฅ ์˜ˆ

m n board
4 5 [โ€œCCBDEโ€, โ€œAAADEโ€, โ€œAAABFโ€, โ€œCCBBFโ€]
6 6 [โ€œTTTANTโ€, โ€œRRFACCโ€, โ€œRRRFCCโ€, โ€œTRRRAAโ€, โ€œTTMMMFโ€, โ€œTMMTTJโ€]

ํ’€์ด

Java
public class ProgrammersFriends4Block {
    // ์˜ˆ์ œ ์ž…๋ ฅ
	static int m = 4;
	static int n = 5;
	static String[] board = {"CCBDE", "AAADE", "AAABF", "CCBBF"};

    // ๊ตฌํ˜„์„ ์œ„ํ•œ ํด๋ž˜์Šค ๋ณ€์ˆ˜
	static char[][] newBoard = new char[m][n];
	static int[] dr = {0, 1, 1};  // ๋™, ๋‚จ, ๋‚จ๋™
	static int[] dc = {1, 0, 1};
	static int Answer;
	
	public static void main(String[] args) {
        // ๋ฌธ์ž์—ด ์ž…๋ ฅ ๋ฐฐ์—ด์„ char ํƒ€์ž…์˜ 2์ฐจ์› ๋ฐฐ์—ด๋กœ ๋ณ€๊ฒฝ
		for (int i=0; i<m; i++) {
			for (int j=0; j<n; j++) {
				newBoard[i][j] = board[i].charAt(j);
			}
		}

        // ๊ฒŒ์ž„ ํ”Œ๋ ˆ์ด
		while (true) {
			boolean stop = search();  // ๊ทผ์ ‘ ๋ธ”๋ก ํ™•์ธ
			if (stop) break;  // ๊ทผ์ ‘ํ•˜๋Š” ๋ธ”๋ก๋“ค ์ค‘ ์ง€์›Œ์ง€๋Š” ๊ฒƒ์ด ์—†์œผ๋ฉด ๊ฒŒ์ž„ ์ข…๋ฃŒ
			delete();   // ๊ทผ์ ‘ํ•˜๋Š” ๋ธ”๋ก ์ œ๊ฑฐ
			replace();  // ์ œ๊ฑฐ๋œ ๋ธ”๋ก ์•„๋ž˜๋กœ ์ •๋ ฌ
		}
		
		Answer = countZero();  // ์ง€์›Œ์ง„ ๋ธ”๋ก ๊ฐœ์ˆ˜ ์นด์šดํŠธ
		System.out.println(Answer);
		
	}
	
    // ๊ทผ์ ‘ ๋ธ”๋ก ํ™•์ธํ•˜๋Š” ๋ฉ”์„œ๋“œ
	static boolean search() {
		boolean flag = true;   // ์ง€์šธ ๊ฒƒ์ด ์žˆ๋Š”์ง€ ํ™•์ธํ•˜๊ธฐ ์œ„ํ•จ
		for (int r=0; r<m-1; r++) {
			for (int c=0; c<n-1; c++) {
				char target = newBoard[r][c];   // ์ขŒ์ƒ๋‹จ ๋ธ”๋ก์„ ๊ธฐ์ค€ ๋ธ”๋Ÿญ์œผ๋กœ ์žก๊ณ  ํ•ด๋‹น ๋ธ”๋Ÿญ์˜ ๋™, ๋‚จ, ๋‚จ๋™๋ถ€๋ถ„ ํƒ์ƒ‰
				if (target != '0') {  // ์ด๋ฏธ ๊ณต๋ฐฑ์œผ๋กœ ์ฑ„์šด ๋ถ€๋ถ„์€ ๊ทผ์ ‘ ๋ธ”๋ก ํ™•์ธ ์•ˆํ•จ
					int cnt = 0;
					for (int i=0; i<3; i++) {
						int nr = r + dr[i];
						int nc = c + dc[i];
						if (target == newBoard[nr][nc]) cnt++;
					}
					if (cnt == 3) {   // ๊ทผ์ ‘ ๋ธ”๋ก 4๊ฐœ๊ฐ€ ๋™์ผํ•  ๊ฒฝ์šฐ
						flag = false;
						newBoard[r][c] = '1';   // ๊ธฐ์ค€ ๋ธ”๋Ÿญ์— ์ง€์›Œ์•ผ ํ•จ์„ ์ฒดํ‚น
					}
				}
			}
		}
		return flag;
	}
	
    // ๊ทผ์ ‘ํ•˜๋Š” ๋ธ”๋ก ์ œ๊ฑฐํ•˜๋Š” ๋ฉ”์„œ๋“œ
	static void delete() {
		for (int r=0; r<m-1; r++) {
			for (int c=0; c<n-1; c++) {
				if (newBoard[r][c] == '1') {   // search() ๋ฉ”์„œ๋“œ ์‹คํ–‰ ๊ฒฐ๊ณผ ์ฒดํ‚น๋œ ๋ธ”๋Ÿญ์„ ๊ธฐ์ค€์œผ๋กœ
					newBoard[r][c] = '0';  // ํ•ด๋‹น ๊ธฐ์ค€ ๋ธ”๋Ÿญ ์ง€์šฐ๊ธฐ
					for (int i=0; i<3; i++) {  // ๋™, ๋‚จ, ๋‚จ๋™ ๋ธ”๋Ÿญ ์ง€์šฐ๊ธฐ
						int nr = r + dr[i];
						int nc = c + dc[i];
						if (newBoard[nr][nc] != '1') newBoard[nr][nc] = '0';
					}
				}
			}
		}
	}
	
    // ์ œ๊ฑฐ๋œ ๋ธ”๋Ÿญ์„ ์•„๋ž˜๋กœ ์ •๋ ฌํ•˜๋Š” ๋ฉ”์„œ๋“œ
	static void replace() {
		for (int c=0; c<n; c++) {
			String oneCol = new String();
			for (int r=m-1; r>=0; r--) {   // ์—ด์„ ๊ธฐ์ค€์œผ๋กœ ๊ฐ€์žฅ ๋ฐ”๋‹ฅ๋ถ€ํ„ฐ ํ™•์ธํ•˜์—ฌ
				if (newBoard[r][c] != '0') {   // ๊ณต๋ฐฑ์ด ์•„๋‹Œ ๋ฌธ์ž๊ฐ€ ์ƒˆ๊ฒจ์ง„ ๋ธ”๋Ÿญ์ด๋ฉด ๊ธฐ์–ต
					oneCol += Character.toString(newBoard[r][c]);
				}
			}
			int bottomR = m;
			for (int i=0; i<oneCol.length(); i++) {  // ์—ด์„ ๊ธฐ์ค€์œผ๋กœ ๋ฐ”๋‹ฅ๋ถ€ํ„ฐ ๋ฌธ์ž๋ฅผ ์ฑ„์›Œ๋‚˜๊ฐ
				newBoard[--bottomR][c] = oneCol.charAt(i);
			}
			if (--bottomR > 0) {  // ์—ด์„ ๊ธฐ์ค€์œผ๋กœ ๋ฌธ์ž๊ฐ€ ์ฑ„์›Œ์ง€์ง€ ์•Š์€ ๋ธ”๋Ÿญ๋“ค์€ ๋‹ค์‹œ ๊ณต๋ฐฑ์œผ๋กœ ์ฑ„์›€
				for (int i=bottomR; i>=0; i--) {
					newBoard[i][c] = '0';
				}
			}
		}
	}
	
    // ์ •๋‹ต ์ถœ๋ ฅ์„ ์œ„ํ•ด ๊ณต๋ฐฑ ๋ธ”๋Ÿญ ๊ฐœ์ˆ˜ ์„ธ๋Š” ๋ฉ”์„œ๋“œ
	static int countZero() {
		int cnt = 0;
		for (int r=0; r<m; r++) {
			for (int c=0; c<n; c++) {
				if (newBoard[r][c] == '0') cnt++;
			}
		}
		return cnt;
	}
}

๐Ÿ’ก

  • ์ž๋ฐ”๋กœ 2์ฐจ์› ๋ฐฐ์—ด ๋‹ค๋ฃจ๋Š” ์—ฐ์Šต์ด ํ•„์š”ํ•ด์„œ ์—ฌ๊ธฐ์ €๊ธฐ ์ฐพ๋‹ค๊ฐ€ ๋ฐœ๊ฒฌํ•œ ๋ฌธ์ œ
  • 2์ฐจ์› ๋ฐฐ์—ด์„ ์ž˜ ์–ด๋ฅด๊ณ  ๋‹ฌ๋ž˜๋Š” ๊ตฌํ˜„ ๋ฌธ์ œ
  • ํšจ์œจ์„ฑ ์ ์ˆ˜๊ฐ€ ์•ˆ๋“ค์–ด๊ฐ€๋Š” ๋ฌธ์ œ๋ผ ๋„˜์–ด๊ฐ”์ง€๋งŒ, ๋งŒ์•ฝ ํšจ์œจ์„ฑ๋„ ์ฑ„์ ํ–ˆ๋‹ค๋ฉด ๊ฑธ๋ฆด ๋ถ€๋ถ„์ด ์•„์ฃผ ๋งŽ์•„๋ณด์ด๋Š” ํ’€์ด,,,