2021.10.24_golang-15686-치킨배달

소스코드 | golang

package main

import (
	"bufio"
	"fmt"
	"os"
)

type Data struct {
	y, x int
}

var (
	n, m    int
	answer                = 0
	board                 = [51][51]int{}
	reader  *bufio.Reader = bufio.NewReader(os.Stdin)
	writer  *bufio.Writer = bufio.NewWriter(os.Stdout)
	chicken []Data
	home    []Data
	D       [15]int
)

func printf(f string, a ...interface{}) { fmt.Fprintf(writer, f, a...) }
func scanf(f string, a ...interface{})  { fmt.Fscanf(reader, f, a...) }

func main() {
	defer writer.Flush()
	inits()
	dfs(0, 0)
	printf("%d\n", answer)
}
func inits() {

	n = 0
	m = 0
	answer = 0x7fffffff
	scanf("%d %d\n", &n, &m)
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			fmt.Fscan(reader, &board[i][j])
			if 1 == board[i][j] {
				home = append(home, Data{i, j})
			}
			if 2 == board[i][j] {
				chicken = append(chicken, Data{i, j})
			}

		}
	}
	// fmt.Println(chicken)
	// fmt.Println(home)
}

func abs(num int) int {
	if num < 0 {
		num = num * -1
	}
	return num
}

func dfs(idx, cnt int) {

	if idx > len(chicken) {
		return
	}
	if cnt == m {
		// fmt.Println(D)
		sum := 0
		// fmt.Println("homeLen", len(home))
		// fmt.Println("chichken", len(chicken))
		homeMin := 0
		for i := 0; i < len(home); i++ {
			homeMin = 0x7fffffff
			for j := 0; j < len(chicken); j++ {
				// fmt.Println(i, j)
				if D[j] == 1 {
					absNum := abs(home[i].y-chicken[j].y) + abs(home[i].x-chicken[j].x)
					// fmt.Println("y", home[i].y, chicken[j].y)
					// fmt.Println("x", home[i].x, chicken[j].x)
					// fmt.Println("absNum", absNum)
					if homeMin > absNum {
						homeMin = absNum
						// fmt.Println("homeMin", homeMin)
					}
				}
			}
			sum += homeMin

			// fmt.Println("homMin fix", homeMin)
		}
		// fmt.Println("sum", sum)
		// fmt.Println("answer", answer)

		if answer > sum {
			answer = sum
		}
		return
	}

	D[idx] = 1
	dfs(idx+1, cnt+1)
	D[idx] = 0
	dfs(idx+1, cnt)
}

소스코드 | C++

#include<stdio.h>
#include<vector>
#include<string.h>
#include<algorithm>
using namespace std;
#define NS 51
struct Data {
	int y, x;
};

vector<Data>chicken;
vector<Data>home;

int N, M;//배열 가로세로크기, 뽑아야할 치킨집
int answer;
int board[NS][NS];//입력 배열
int D[15];//치킨 선택

void init();//초기화
void chickenChoose();//치킨선택
void dfs(int idx, int cnt);
int main(void) {
	int testCase = 1;
	for (int tc = 1; tc<=testCase; tc++) {
		init();
		chickenChoose();
		printf("%d\n", answer);
	}
}
void init() {
	N = M = 0;
	answer = 0x7fffffff;
	memset(board, 0, sizeof(board));
	home.clear(); chicken.clear();
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &board[i][j]);
			if (1 == board[i][j]) {//집 저장
				home.push_back({ i,j });
			}
			else if (2 == board[i][j]) {//치킨 저장
				chicken.push_back({ i,j });
			}
		}
	}
}
void chickenChoose() {
	dfs(0, 0);
}
void dfs(int idx, int cnt) {
	if (idx > chicken.size())return;
	if (cnt==M) {
		int sum = 0;
		for (int i = 0; i < home.size(); i++) {
			int homeMin = 0x7fffffff;
			for (int j = 0; j < chicken.size(); j++) {
				if (D[j] == 1) {
					int absNum = abs(home[i].y - chicken[j].y) + abs(home[i].x - chicken[j].x);
					homeMin = homeMin > absNum ? absNum : homeMin;
				}
			}
			sum += homeMin;
		}
		answer = answer > sum ? sum : answer;
		return;
	}
	D[idx] = 1;
	dfs(idx + 1, cnt + 1);
	D[idx] = 0;
	dfs(idx + 1, cnt);
}

실수

• 여기서 실수한 부분은 우선 실수보다 scanf, printf 방식이 다르고
• 왜그런지 이유는 모르겠지만 Fscanf로 이차원 배열에 데이터 값 넣었을 때
  • 값이 밀리는 현상이 발견됨
  • 그래서 현재는 그냥 Fscan으로 데이터를 넣고 진행함
• 일차원적 실수를 한것은 i,j를 혼동해서 잘 못 쓴것
• answer값을 최댓값으로 초기화해야하는데 초기화를 제대로 안한것
• 문제 자체는 어려운게 아니지만 확실히 출력면이나 slice, 배열쓰는게 익숙한게 아니라서 그런지 자잘한 실수가 있었음

문제 링크

15686-치킨배달

원본

https://github.com/3DPIT/golang/blob/master/00.GolangAlgorithm/study/1024/01.15686-%EC%B9%98%ED%82%A8%EB%B0%B0%EB%8B%AC/2021.10.24_golang-15686-%EC%B9%98%ED%82%A8%EB%B0%B0%EB%8B%AC.md

GitHub - 3DPIT/golang