2021.10.24_golang-15686-치킨배달
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 )
}
#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-치킨배달