1. 백준 치킨배달[15686]
도시가 주어지고, 도시에는 집과 치킨가게 가 존재한다. 총 m 개의 치킨가게 가 존재할 때 도시에 주어지는 집들로부터 거리가 가장 작은 최솟값의 거리를 구하는 문제이다.
치킨가게 와 집의 거리계산 은 주어지는 좌표 의 차에서 구한 거리이다.
해당 문제 는 주어지는 배열을 사용하지 않고, 치킨집과 집들을 가지고 새로운 거리 배열을 만들어서 해결해 주었다.
다시 말해 행, 열 에는 치킨집과 집들을 배치하고, 해당 거리들을 배열에 담아 해결했다.
func boj15686() {
answer := 1 << 31
var distance [][]int
abs := func(a int) int {
if a < 0 {
return -a
}
return a
}
min := func(a, b int) int {
if a < b {
return a
}
return b
}
minValue := func(include []int, distance [][]int) int {
result := 0
for i := 0; i < len(distance); i++ {
step := 1 << 31
for j := 0; j < len(distance[i]); j++ {
for k := 0; k < len(include); k++ {
if j == include[k] {
step = min(step, distance[i][j])
}
}
}
result += step
}
return result
}
helper := func(num, depth, limit, flag, start int, out []int) {}
helper = func(num, depth, limit, flag, start int, out []int) {
if depth == limit {
answer = min(answer, minValue(out, distance))
return
} else {
for i := start; i < num; i++ {
if flag&(1<<i) == 0 {
helper(num, depth+1, limit, flag|(1<<i), i+1, append(out, i))
}
}
}
}
reader := bufio.NewReader(os.Stdin)
var (
a, b int
)
fmt.Fscanln(reader, &a, &b)
house := make([][]int, 0)
chicken := make([][]int, 0)
for i := 0; i < a; i++ {
for j := 0; j < a; j++ {
var tmp int
fmt.Fscan(reader, &tmp)
if tmp == 1 {
house = append(house, []int{i, j})
} else if tmp == 2 {
chicken = append(chicken, []int{i, j})
}
}
}
distance = make([][]int, len(house))
for i := 0; i < len(house); i++ {
distance[i] = make([]int, len(chicken))
for j := 0; j < len(chicken); j++ {
distance[i][j] = abs(house[i][0]-chicken[j][0]) + abs(house[i][1]-chicken[j][1])
}
}
/**
치킨집의 개수가 최대 13개이므로, 치킨집의 개수에서 M개를 뽑는 조합을 구하면 된다. (13C6) = 1716 * 집이 최대 50개이므로, 1716 * 50 = 85800
*/
helper(len(chicken), 0, b, 0, 0, []int{})
fmt.Println(answer)
}고에서 제공하는 min, abs는 타입변환이 필요해서 추가적으로 함수를 작성해 주었다.
치킨집, 일반집 은 각각 1,2의 값으로 주어지기 때문에 입력값을 받아옴과 동시에 해당 좌표들을 배열로 만들어주고,
거리를 구하기 위해서 위에서 작성된 자표를 이용해 모든 집과 모든 치킨집의 대한 거리에 대해 배열을 작성해 주었다.
2. 백준 테트로미노 [14500]
왼쪽에 보이는 모양을 맵에다가 놓았을 때 최댓값을 구해야 한다. 단 주어지는 저 도형들은 회전, 대칭 등이 가능하다.
코드가 엄청 길다. 해당되는 상황에 대해 모두 분기를 나눠주다 보니 아무래도 그게 더 심했던 거 같다.
코드보다 그림을 더 많이 그렸던 문제...
func solution() {
reader := bufio.NewReader(os.Stdin)
getMax := func(a, b int) int {
if a > b {
return a
}
return b
}
stick := func(arr [][]int, row, col int) (rs int) {
//right 3steps more
if col+3 < len(arr[0]) {
rs = getMax(rs, arr[row][col]+arr[row][col+1]+arr[row][col+2]+arr[row][col+3])
}
//down 3steps more
if row+3 < len(arr) {
rs = getMax(rs, arr[row][col]+arr[row+1][col]+arr[row+2][col]+arr[row+3][col])
}
return rs
}
square := func(arr [][]int, row, col int) (rs int) {
// right 1step down 1step
if row+1 < len(arr) && col+1 < len(arr[0]) {
rs = getMax(rs, arr[row][col]+arr[row][col+1]+arr[row+1][col]+arr[row+1][col+1])
}
return rs
}
nieun := func(arr [][]int, row, col int) (rs int) {
// right 2steps down 1step
if row+1 < len(arr) && col+2 < len(arr[0]) {
rs = getMax(rs, arr[row][col]+arr[row+1][col]+arr[row+1][col+1]+arr[row+1][col+2])
}
// left 2steps down 1step
if row+1 < len(arr) && col-2 >= 0 {
rs = getMax(rs, arr[row][col]+arr[row+1][col]+arr[row+1][col-1]+arr[row+1][col-2])
}
// top 1step right 2steps
if row-1 >= 0 && col+2 < len(arr[0]) {
rs = getMax(rs, arr[row][col]+arr[row-1][col]+arr[row-1][col+1]+arr[row-1][col+2])
}
// top 1step left 2steps
if row-1 >= 0 && col-2 >= 0 {
rs = getMax(rs, arr[row][col]+arr[row-1][col]+arr[row-1][col-1]+arr[row-1][col-2])
}
//right 1step down 2steps
if row+2 < len(arr) && col+1 < len(arr[0]) {
rs = getMax(rs, arr[row][col]+arr[row][col+1]+arr[row+1][col+1]+arr[row+2][col+1])
}
//right 1step top 2steps
if row-2 >= 0 && col+1 < len(arr[0]) {
rs = getMax(rs, arr[row][col]+arr[row][col+1]+arr[row-1][col+1]+arr[row-2][col+1])
}
// left 1step down 2steps
if row+2 < len(arr) && col-1 >= 0 {
rs = getMax(rs, arr[row][col]+arr[row][col-1]+arr[row+1][col-1]+arr[row+2][col-1])
}
// left 1step top 2steps
if row-2 >= 0 && col-1 >= 0 {
rs = getMax(rs, arr[row][col]+arr[row][col-1]+arr[row-1][col-1]+arr[row-2][col-1])
}
return rs
}
triangle := func(arr [][]int, row, col int) (rs int) {
// right 2steps up 1step
if row-1 >= 0 && col+2 < len(arr[0]) {
rs = getMax(rs, arr[row][col]+arr[row][col+1]+arr[row][col+2]+arr[row-1][col+1])
}
//right 2steps down 1step
if row+1 < len(arr) && col+2 < len(arr[0]) {
rs = getMax(rs, arr[row][col]+arr[row][col+1]+arr[row][col+2]+arr[row+1][col+1])
}
// down 2steps right 1step
if row+2 < len(arr) && col+1 < len(arr[0]) {
rs = getMax(rs, arr[row][col]+arr[row+1][col]+arr[row+2][col]+arr[row+1][col+1])
}
// down 2steps left 1step
if row+2 < len(arr) && col-1 >= 0 {
rs = getMax(rs, arr[row][col]+arr[row+1][col]+arr[row+2][col]+arr[row+1][col-1])
}
return rs
}
etc := func(arr [][]int, row, col int) (rs int) {
// right 2steps up 1step
if row-1 >= 0 && col+2 < len(arr[0]) {
rs = getMax(rs, arr[row][col]+arr[row][col+1]+arr[row-1][col+1]+arr[row-1][col+2])
}
//right 2steps down 1step
if row+1 < len(arr) && col+2 < len(arr[0]) {
rs = getMax(rs, arr[row][col]+arr[row][col+1]+arr[row+1][col+1]+arr[row+1][col+2])
}
//down 2steps right 1step
if row+2 < len(arr) && col+1 < len(arr[0]) {
rs = getMax(rs, arr[row][col]+arr[row+1][col]+arr[row+1][col+1]+arr[row+2][col+1])
}
//down2steps left 1step
if row+2 < len(arr) && col-1 >= 0 {
rs = getMax(rs, arr[row][col]+arr[row+1][col]+arr[row+1][col-1]+arr[row+2][col-1])
}
return rs
}
check := func(arr [][]int, row, col int) int {
result := getMax(square(arr, row, col), stick(arr, row, col))
result2 := getMax(nieun(arr, row, col), triangle(arr, row, col))
return getMax(result, getMax(result2, etc(arr, row, col)))
}
var answer int
helper := func(arr [][]int, size int) {}
helper = func(arr [][]int, size int) {
if size == len(arr[0])*len(arr) {
return
}
row, col := size/len(arr[0]), size%len(arr[0])
answer = getMax(answer, check(arr, row, col))
helper(arr, size+1)
}
var n, m int
fmt.Fscanln(reader, &n, &m)
arr := make([][]int, n)
for i := range arr {
arr[i] = make([]int, m)
for j := range arr[i] {
fmt.Fscan(reader, &arr[i][j])
}
}
helper(arr, 0)
fmt.Println(answer)
}
단순 코드가 길어서 그렇지 해당되는 모든 케이스에 대해서 잘 정리만 해준다면 일반적인 dfs처럼 좌표의 1번부터 수행하면 된다.
개인적으로 이렇게 좌표탐색을 할 때는 row, col을 넘겨주는거보다 하나의 숫자를 넘겨 row,col 을 계산하는 것이 훨씬 깔끔하다. 예전 스도쿠 문제 풀면서 다른 사람 풀이 중에 이런 부분이 있어 바로 차용해서 이제는 저렇게 숫자로 넘기는 게 더 편하다.
이번주는 생각보다 문제를 많이 풀지 못했다. 아침에 가면 문의 답변 해야 할게 생각보다 있어 오전시간에는 거의 풀지 못했다.
다만 지난주보다 마음에 들었던 점은 해당 두 문제에 대해서 바로 한 번에 통과해서 기분이 무척 좋았다.
'PS > Boj' 카테고리의 다른 글
| 백준-완탐 연습(Brute-Force) (0) | 2023.08.14 |
|---|---|
| 백준 1251 단어나누기[Java] (0) | 2022.06.26 |
| 백준 1120 문자열[Java] (0) | 2022.06.26 |
| 백준 10448 유레카[Java] (0) | 2022.06.26 |
