백준-완탐 연습(Brute-Force)-2

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 을 계산하는 것이 훨씬 깔끔하다. 예전 스도쿠 문제 풀면서 다른 사람 풀이 중에 이런 부분이 있어 바로 차용해서 이제는 저렇게 숫자로 넘기는 게 더 편하다.

 

이번주는 생각보다 문제를 많이 풀지 못했다. 아침에 가면 문의 답변 해야 할게 생각보다 있어 오전시간에는 거의 풀지 못했다.

 

다만 지난주보다 마음에 들었던 점은 해당 두 문제에 대해서 바로 한 번에 통과해서 기분이 무척 좋았다.