글 읽기 - golang) 이 문제 이렇게 풀어도 문제 없나요?

kwkimg3100 2년 전 0

정답이긴합니다만

구글링을통해 풀이하신분들보면 다른방법으로 많이 푸시길래

요렇게 풀어도 문제없는건지 궁금합니다.

package main

import (
	"fmt"
)

var (
	board  [15][15]bool
	size   int
	count  int
	result int
)

func main() {
	fmt.Scan(&size)
	dfs(1)
	fmt.Println(result)
}

func dfs(start int) {
	var backup [15][15]bool
	if count == size {
		result++
		return
	}
	for i := 1; i <= size; i++ {
		if !board[start][i] {
			count++
			backup = board
			queen(start, i, true)
			dfs(start + 1)
			count--
			board = backup
		}
	}
}

//퀸의 위치에따라 체스판을 칠함
func queen(x int, y int, state bool) {
	for i := 1; i < 15; i++ {
		board[x][i] = state
	}
	for i := 1; i < 15; i++ {
		board[i][y] = state
	}
	var tmp = y
	for i := x; i < 15; i++ {
		if tmp < 15 && i < 15 {
			board[i][tmp] = state
			tmp++
		} else {
			break
		}
	}
	tmp = y
	for i := x; i < 15; i++ {
		if tmp > 0 && i < 15 {
			board[i][tmp] = state
			tmp--
		} else {
			break
		}
	}
	tmp = x
	for i := y; i < 15; i++ {
		if tmp > 0 && i < 15 {
			board[tmp][i] = state
			tmp--
		} else {
			break
		}
	}
	tmp = x
	for i := y; i > 0; i-- {
		if tmp > 0 && i > 0 {
			board[tmp][i] = state
			tmp--
		} else {
			break
		}
	}
}

bamgoesn 2년 전 0

결국 로직은 대부분의 풀이와 같이 DFS를 활용한 백트래킹을 사용하신 거 아닌가요?

일단 답이 맞으면 되는 거긴 하거든요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

golang) 이 문제 이렇게 풀어도 문제 없나요?

kwkimg3100 2년 전 0

bamgoesn 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말