💼 완벽한 좌석 배치표: Go로 리더십 서밋 문제 해결하기 🔗

func solveImpl(state *State) bool {
	if state.solved {
		return true
	}

	// 첫 번째 라운드에서는 모든 사람을 고려함
	start := 0
	end := state.people

	// 두 번째 라운드부터는 탐색 공간을 제한함
	if len(state.res) > 0 {
		start = len(state.table) * state.tableSize
		end = start + state.tableSize
	}

	for person := start; person < end; person++ {
		if !valid(state, person) {
			continue // 이 배정이 충돌을 일으키면 건너뜀
		}
        
		set(state, person) // 좌석 배정
		if solveImpl(state) {
			return true // 성공!
		}
		unset(state, person) // 백트래킹
	}
	
	return false
}

func valid(state *State, person int) bool {
	// 이 사람이 이번 라운드에 이미 좌석을 배정받았는가?
	if state.usedPerson[person] {
		return false
	}
	
	// 이 사람이 현재 이 테이블에 있는 누군가와 이전에 함께 앉은 적이 있는가?
	for _, there := range state.table {
		first := min(there, person)
		second := max(there, person)
		
		if state.usedPair[first][second] {
			return false
		}
	}
	
	return true
}

func set(state *State, person int) {
	state.usedPerson[person] = true
	
	// 이 사람이 현재 테이블에 있는 모든 사람과 짝을 이뤘음을 표시
	for _, there := range state.table {
		first := min(there, person)
		second := max(there, person)
		if _, ok := state.usedPair[first]; !ok {
			state.usedPair[first] = map[int]bool{}
		}
		state.usedPair[first][second] = true
	}
	
	state.table = append(state.table, person)
	
	// 테이블이 꽉 찼으면 다음 테이블로 이동
	if len(state.table) != state.tableSize {
		return
	}
	state.round = append(state.round, state.table)
	state.table = []int{}
	
	// 모든 테이블이 꽉 찼으면 다음 라운드로 이동
	if len(state.round) != state.numTables {
		return
	}
	state.res = append(state.res, state.round)
	state.round = [][]int{}
	state.usedPeople = append(state.usedPeople, state.usedPerson)
	state.usedPerson = map[int]bool{}
	
	// 완전히 끝났는지 확인
	if len(state.res) != state.numRounds {
		return
	}
	state.solved = true
}

func unset(state *State, person int) {
	state.solved = false
	
	// 현재 테이블이 비어 있으면 이전 테이블로 되돌아감
	if len(state.table) == 0 {
		if len(state.round) == 0 {
			last := len(state.res) - 1
			state.round = state.res[last]
			state.res = state.res[:last]
			state.usedPerson = state.usedPeople[last]
			state.usedPeople = state.usedPeople[:last]
		}
		last := len(state.round) - 1
		state.table = state.round[last]
		state.round = state.round[:last]
	}
	
	// 테이블에서 해당 사람을 제거
	state.table = state.table[:len(state.table)-1]
	
	// 짝 표시 해제
	for _, there := range state.table {
		first := min(there, person)
		second := max(there, person)
		state.usedPair[first][second] = false
	}
	state.usedPerson[person] = false
}

round 0:
  table 0: 0  1  2  3
  table 1: 4  5  6  7
  table 2: 8  9  10 11
  table 3: 12 13 14 15

round 1:
  table 0: 0  4  8  12
  table 1: 1  5  9  13
  table 2: 2  6  10 14
  table 3: 3  7  11 15

round 2:
  table 0: 0  5  10 15
  table 1: 1  4  11 14
  table 2: 2  7  8  13
  table 3: 3  6  9  12

round 3:
  table 0: 0  6  11 13
  table 1: 1  7  10 12
  table 2: 2  4  9  15
  table 3: 3  5  8  14

round 4:
  table 0: 0  7  9  14
  table 1: 1  6  8  15
  table 2: 2  5  11 12
  table 3: 3  4  10 13