[백준] 18808.스티커 붙이기 (Swift)

[백준] 18808.스티커 붙이기 (Swift)

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

18808번: 스티커 붙이기

풀이

1. 배열 비교

먼저 스티커 자체를 배열에 붙일 수 있는지 없는지를 확인해야 했기 때문에 스티커의 크기만큼 배열에서 인덱스를 이동하며 탐색하였습니다.

 

맨 처음에는 확인하려는 범위의 첫번째 인덱스, 즉 맨 좌측 상단이 1로 채워져 있으면 스티커를 붙일 수 없다고 생각했습니다.

 

하지만 스티커의 첫번째 인덱스는 항상 1이 아니고 0일 수도 있기 때문에 이는 오산이었습니다. 결국 스티커 범위 내에서 모든 값을 비교해본 뒤 하나라도 겹치는 부분이 있다면 붙일 수 없게 하였습니다.

 

반대로 스티커를 붙일 수 있다면 해당 부분에 값을 더해주어 배열을 채워주었습니다. 

2. 배열 회전하기

스티커를 붙일 수 없다면 배열을 90도로 3번 회전시켜 다시 시도해봐야 했었습니다. 사실 이 부분의 코드는 정확히 계산해내지 못해 다른 분들의 풀이를 참고하였습니다.

 

먼저 스티커를 회전하기 위해 스티커의 값을 저장할 임시 배열을 선언해 준뒤 그 값을 그대로 복사해주었습니다. 그 다음 스티커의 가로 세로 크기를 서로 바꿔주었습니다.

 

관건은 인덱스였습니다. 행과 열의 값이 바뀌기 때문에 반복문은 그 전과 다르게 기존의 열 -> 행 순으로 순회하였고, 기존의 행 크기에서 1을 뺀 값과 탐색값을 빼주면서 이후의 행 인덱스를 찾았습니다.

 

메소드에는 포함되어있지 않지만, 메소드가 실행되고 나서는 스티커의 행과 열 값을 바꿔주었습니다.

코드

	import Foundation
	// MARK: - 함수 선언부
	// 스티커 회전 메소드
	func rotateSticker(rn: Int, rm: Int, _sticker: [[Int]]) -> [[Int]] {
	var tmpBoard: [[Int]] = Array(repeating: Array(repeating: 0, count: 10), count: 10)
	var sticker: [[Int]] = _sticker
	for i in 0 ..< rn {
	for j in 0 ..< rm {
	tmpBoard[i][j] = sticker[i][j]
	}
	}
	sticker = Array(repeating: Array(repeating: 0, count: rn), count: rm)
	for i in 0 ..< rm {
	for j in 0 ..< rn {
	sticker[i][j] = tmpBoard[rn - 1 - j][i]
	}
	}
	return sticker
	}
	// 스티커 붙이기
	func putSticker(si: Int, sj: Int, testSticker: [[Int]]) -> Bool {
	var isAvailable = false
	// 보드 위 탐색
	for i in 0 ..< n {
	for j in 0 ..< m {
	isAvailable = true
	// 스티커 붙일수 있는지 탐색
	for k in i ..< i + si {
	// 범위 검사
	if i + si > n {
	isAvailable = false
	break
	}
	for l in j ..< j + sj {
	// 범위 검사
	if j + sj > m {
	isAvailable = false
	break
	}
	// 겹치면 합이 2가 되니까 안되고
	if testBoard[k][l] + testSticker[k - i][l - j] == 2 {
	isAvailable = false
	break
	} else {
	// 안겹치면 그자리에 덮어씌워주기
	testBoard[k][l] += testSticker[k - i][l - j]
	}
	}
	// 틀렸을때는 항상 원래 상태로 보드 돌려놓기
	if !isAvailable {
	testBoard = board
	break
	}
	}
	// 맞으면 테스트로 붙여봤던거 다시 저장
	if isAvailable {
	board = testBoard
	return isAvailable
	}
	}
	}
	return isAvailable
	}
	// MARK: - 구현부
	// 보드 크기, 스티커 개수
	let input = readLine()!.split(separator: " ").map { Int(String($0))! }
	let (n, m, k) = (input[0], input[1], input[2])
	// 스티커 붙여보다가 틀렸을때를 대비해서 두개 만들기
	var board: [[Int]] = Array(repeating: Array(repeating: 0, count: m), count: n)
	var testBoard: [[Int]] = Array(repeating: Array(repeating: 0, count: m), count: n)
	for _ in 0 ..< k {
	// 스티커 크기
	let info = readLine()!.split(separator: " ").map { Int(String($0))! }
	var (si, sj) = (info[0], info[1])
	var sticker: [[Int]] = []
	for _ in 0 ..< si {
	let line = readLine()!.split(separator: " ").map { Int(String($0))! }
	sticker.append(line)
	}
	// 4번 회전하면서 시도
	for _ in 0 ..< 4 {
	let success = putSticker(si: si, sj: sj, testSticker: sticker)
	if success {
	break
	} else {
	sticker = rotateSticker(rn: si, rm: sj, _sticker: sticker)
	swap(&si, &sj)
	}
	}
	}
	var answer: Int = 0
	for i in 0 ..< n {
	for j in 0 ..< m {
	answer += board[i][j]
	}
	}
	print(answer)

view raw BOJ_18808.swift hosted with ❤ by GitHub