개발 블로그

문제 링크 : https://www.acmicpc.net/problem/3040

문제

매일 매일 일곱 난쟁이는 광산으로 일을 하러 간다. 난쟁이가 일을 하는 동안 백설공주는 그들을 위해 저녁 식사를 준비한다. 백설공주는 의자 일곱개, 접시 일곱개, 나이프 일곱개를 준비한다.

어느 날 광산에서 아홉 난쟁이가 돌아왔다. (왜 그리고 어떻게 아홉 난쟁이가 돌아왔는지는 아무도 모른다) 아홉 난쟁이는 각각 자신이 백설공주의 일곱 난쟁이라고 우기고 있다.

백설공주는 이런 일이 생길 것을 대비해서, 난쟁이가 쓰고 다니는 모자에 100보다 작은 양의 정수를 적어 놓았다. 사실 백설 공주는 공주가 되기 전에 매우 유명한 수학자였다. 따라서, 일곱 난쟁이의 모자에 쓰여 있는 숫자의 합이 100이 되도록 적어 놓았다.

아홉 난쟁이의 모자에 쓰여 있는 수가 주어졌을 때, 일곱 난쟁이를 찾는 프로그램을 작성하시오. (아홉 개의 수 중 합이 100이 되는 일곱 개의 수를 찾으시오)

입력

총 아홉개 줄에 1보다 크거나 같고 99보다 작거나 같은 자연수가 주어진다. 모든 숫자는 서로 다르다. 또, 항상 답이 유일한 경우만 입력으로 주어진다.

출력

일곱 난쟁이가 쓴 모자에 쓰여 있는 수를 한 줄에 하나씩 출력한다.

접근 방법

DFS 를 이용해서 9명 중 7명을 뽑았을 때 난쟁이 번호의 합이 100이 되는지 검사한다. 정답을 찾으면 true 를 리턴해서 DFS를 빠져나왔을 때 탐색을 진행하지 않고 종료한다.

좀 더 시간을 줄이기 위해 DFS의 첫번째 파라미터를 이용해서 중복 조합으로 난쟁이들을 뽑았다. 두명을 뽑는다고 했을 때, (1번 난쟁이, 2번 난쟁이)를 뽑는 것과 (2번 난쟁이, 1번 난쟁이) 를 뽑는 것이 같기 때문이다.

import java.util.*;
public class DFS_BOj3040_백설공주와일곱난쟁이 {

	static int[] numArr, visited;
	static ArrayList<Integer> ansList = new ArrayList<Integer>(); 
	
	public static boolean DFS(int start, int toPick, int sum) {
		if(toPick==0 && sum==100) {
			for(int i = 0; i<ansList.size(); i++) {
				System.out.println(ansList.get(i));
			}
			return true;
		}
		
		for(int i = start; i<9; i++) {
			if(visited[i] == 0) {
				visited[i] = 1;
				ansList.add(numArr[i]);
				if(DFS(i, toPick-1, sum + numArr[i])==false) {
					ansList.remove(ansList.size()-1);
					visited[i] = 0;
				}
				else break;
			}
		}
		return false;
	}
	
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		numArr = new int[9];
		visited = new int[9];
		
		for(int i = 0; i<9; i++) {
			numArr[i] = sc.nextInt();
		}
		
		DFS(0,7,0);	
	}
}

문제 링크 : www.acmicpc.net/problem/16936

문제

나3곱2 게임은 정수 하나를 이용한다. 가장 먼저, 정수 x로 시작하고, 연산을 N-1번 적용한다. 적용할 수 있는 연산은 두 가지 있고, 아래와 같다.

• 나3: x를 3으로 나눈다. x는 3으로 나누어 떨어져야 한다.
• 곱2: x에 2를 곱한다.

나3곱2 게임을 진행하면서, 만든 수를 모두 기록하면 수열 A를 만들 수 있다. 예를 들어, x = 9, N = 6이고, 적용한 연산이 곱2, 곱2, 나3, 곱2, 나3인 경우에 A = [9, 18, 36, 12, 24, 8] 이다.

수열 A의 순서를 섞은 수열 B가 주어졌을 때, 수열 A를 구해보자.

입력

첫째 줄에 수열의 크기 N(2 ≤ N ≤ 100)이 주어진다. 둘째 줄에는 수열 B가 주어진다. B에 포함된 원소는 1018 보다 작거나 같은 자연수이다.

출력

나3곱2 게임의 결과 수열 A를 출력한다. 항상 정답이 존재하는 경우에만 입력으로 주어지며, 가능한 정답이 여러가지인 경우에는 아무거나 출력한다.

접근 방법

주의할 점 : B에 포함된 원소는 10^18 보다 작거나 같은 자연수이므로 자료형을 long long 으로 해줘야 한다. int 형으로 하면 출력초과나 틀렸습니다가 나온다. 

주어진 조건대로 직관적으로 풀어보았다.

1. 주어진 수열 B의 첫번째 요소를 x로 설정한다.

1-1. x곱2 연산을 한 결과가 (수열 B에 있고 x로 설정한 적이 없으면) 수열 A에 push 하고 DFS를 호출한다. 

1-2. x곱2 연산을 한 결과가 (수열 B에 없거나 x로 설정한 적이 있으면) 나3 연산을 진행한다.

     1-2-1) x가 3의 배수이고, x/3이 수열 A에 있고 ,x/3을 x로 설정한 적이 없으면 수열 A에 x/3을 push 하고 DFS를 호출한다. 

이 과정을 반복해서 수열 A의 크기가 N이 되면 DFS를 빠져나갈 때 바로 빠져나가기 위해 iscontinue를 false로 설정한 뒤 수열 A의 원소를 출력한다. 

예로 A = {4 8 6 3 12 9} 이고 x=4로 설정한 후 실행했다고 해보자.

4*2 = 8 -> 8은 수열 A에 존재하고 x=4이므로 visited한 적 없으므로 수열A에 8을 push하고 DFS를 호출한다. 

8*2 = 16은 수열 A에 존재하지 않으므로 16을 수열 A에서 pop 하고 DFS를 빠져나간다.

다시 8에 대해 나3 연산을 수행해본다. 8은 3의 배수가 아니므로 수열 A에서 8을 pop하고 DFS를 빠져나간다. 

다시 4에 대해 나3연산을 수행해본다. 4도 3의 배수가 아니므로 수열 A에서 8을 pop하고 DFS를 빠져나간다. 

이제 x=8로 설정하고 위와 같이 반복한다.

//
//  BF_BOJ16936_나3곱2.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/04/03.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>
#include <vector>
#include <utility>

using namespace std;

vector<long long> vecB;
vector<long long> vecA;
int visited[100] = {0};
int N;

pair<bool, int> isIn(long long num){					
    for(int i = 0; i<N; i++){
        if(vecB[i]==num) return make_pair(true, i);		//<해당 숫자가 있는지,수열 B에서 몇번째 인덱스인지>
    }
    return make_pair(false, -1);
}

bool iscontinue = true;
void DFS(long long x, int cnt){
    
    if(cnt==N){
        iscontinue = false;
        for(int i = 0; i<N; i++){
            cout << vecA[i] << " ";
        }
        printf("\n");
        return;
    }
    
    //곱2
    pair<bool, int> p = isIn(2*x);
    if(p.first==true && visited[p.second]==0){
        visited[p.second] = 1;
        vecA.push_back(x*2);
        DFS(x*2, cnt+1);
        if(iscontinue){
            vecA.pop_back();
            visited[p.second] = 0;
        }else return;
       
    }

    
    //나3
    if(x%3 == 0){
        pair<bool, int> p2 = isIn(x/3);
        if(p2.first==false) return;
        else if(p2.first==true && visited[p2.second]==0){
            visited[p2.second] = 1;
            vecA.push_back(x/3);
            DFS(x/3, cnt+1);
            if(iscontinue){
                vecA.pop_back();
                visited[p2.second] = 0;
            }else return;
           
        }
    }
    
    if(iscontinue==false) return;
}


int main(){

    cin>>N;
   
    long long num;
    for(int i = 0; i<N; i++){
        scanf("%lld", &num);
        vecB.push_back(num);
    }
    
    for(int i = 0; i<vecB.size(); i++){			//주어진 수열 B에서 하나씩 x로 지정해서 DFS 돌림
        visited[i] = 1;
        vecA.push_back(vecB[i]);
        DFS(vecB[i], 1);
        if(iscontinue==true){					//수열 A 찾지 못했을 경우 pop 하고 다음 요소를 x로 지정해서 반복
            vecA.pop_back();
            visited[i] = 0;
        }else break;
    }
    
    return 0;
}

아래의 방법은 velog.io/@hschoi1104/BOJ-16936-%EB%82%983%EA%B3%B12

를 참고해서 위의 코드를 수정한 것이다. 

//
//  BF_BOJ16936_나3곱2.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/04/03.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

vector<long long> vecB;
vector<long long> vecA;
int N;


void DFS(long long x, int cnt){

    if(cnt==N){
        for(int i = 0; i<N; i++){
            cout << vecA[i] << " ";
        }
        exit(0);
    }
    

    if(x%3==0 && find(vecB.begin(), vecB.end(), x/3)!=vecB.end()){
        vecA.push_back(x/3);
        DFS(x/3, cnt+1);
        vecA.pop_back();
    }
    if(find(vecB.begin(), vecB.end(), 2*x)!=vecB.end()){
        vecA.push_back(2*x);
        DFS(2*x, cnt+1);
        vecA.pop_back();
    }
    return;
}


int main(){

    cin>>N;
   
    long long num;
    for(int i = 0; i<N; i++){
        scanf("%lld", &num);
        vecB.push_back(num);
    }
    
    for(int i = 0; i<vecB.size(); i++){
       
        vecA.push_back(vecB[i]);
        DFS(vecB[i], 1);
        vecA.pop_back();
            
    }
    
    return 0;
}

문제 링크 : www.acmicpc.net/problem/14503

문제

로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.

로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다.

로봇 청소기는 다음과 같이 작동한다.

1. 현재 위치를 청소한다.
2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.
   1. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
   2. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
   3. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
   4. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.

로봇 청소기는 이미 청소되어있는 칸을 또 청소하지 않으며, 벽을 통과할 수 없다.

입력

첫째 줄에 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 50)

둘째 줄에 로봇 청소기가 있는 칸의 좌표 (r, c)와 바라보는 방향 d가 주어진다. d가 0인 경우에는 북쪽을, 1인 경우에는 동쪽을, 2인 경우에는 남쪽을, 3인 경우에는 서쪽을 바라보고 있는 것이다.

셋째 줄부터 N개의 줄에 장소의 상태가 북쪽부터 남쪽 순서대로, 각 줄은 서쪽부터 동쪽 순서대로 주어진다. 빈 칸은 0, 벽은 1로 주어진다. 지도의 첫 행, 마지막 행, 첫 열, 마지막 열에 있는 모든 칸은 벽이다.

로봇 청소기가 있는 칸의 상태는 항상 빈 칸이다.

출력

로봇 청소기가 청소하는 칸의 개수를 출력한다.

접근 방법

로봇청소기가 움직이는 규칙을 먼저 잘 이해해야 구현하는데에 헷갈리지 않는다.

규칙을 간단히 해보면 아래와 같다. 

"현재 위치에서 DFS를 돌면서 네 방향 청소를 해 나가고, 네방향 청소가 다 끝나면(벽이거나 다 했거나) 뒤로 후진한다. 후진하려하는데 벽이면 종료한다."

문제의 예제입력2에 대해, 로봇청소기가 청소한 자리 (r,c) 와 이때까지 청소한 칸의 합을 프린트해보면 아래와 같다.

(7, 4)  /   1

(7, 3)  /   2

(8, 3)  /   3

(8, 4)  /   4

(9, 4)  /   5

(9, 5)  /   6

(8, 5)  /   7

(7, 5)  /   8

(6, 5)  /   9

(6, 4)  /   10

(5, 4)  /   11

(5, 3)  /   12

(6, 3)  /   13

(6, 2)  /   14

(7, 2)  /   15

(7, 1)  /   16

(8, 1)  /   17

(8, 2)  /   18

(9, 2)  /   19

(9, 3)  /   20

(9, 1)  /   21

(9, 6)  /   22

(9, 7)  /   23

(9, 8)  /   24

(8, 8)  /   25

(7, 8)  /   26

(6, 8)  /   27

(5, 8)  /   28

(5, 7)  /   29

(4, 7)  /   30

(4, 6)  /   31

(5, 6)  /   32

(5, 5)  /   33

(4, 5)  /   34

(4, 4)  /   35

(3, 5)  /   36

(3, 6)  /   37

(3, 7)  /   38

(3, 8)  /   39

(2, 8)  /   40

(1, 8)  /   41

(1, 7)  /   42

(1, 6)  /   43

(1, 5)  /   44

(1, 4)  /   45

(1, 3)  /   46

(2, 3)  /   47

(2, 2)  /   48

(3, 2)  /   49

(3, 1)  /   50

(4, 1)  /   51

(5, 1)  /   52

(5, 2)  /   53

(6, 1)  /   54

(2, 1)  /   55

(1, 1)  /   56

(1, 2)  /   57

청소기의 이동 흔적을 그림으로 나타내보았다. (초록, 분홍, 파랑, 노랑 순서)

//
//  SM_BOJ14503_로봇청소기.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/03/21.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>

using namespace std;

int map[50][50];
int visited[50][50];
int N, M;

//위 오 아 왼
int dr[4] = {-1,0,1,0};
int dc[4] = {0,1,0,-1};

void dfs(int r, int c, int d, int sum){ //2번
    
//    1. 현재 위치를 청소한다.
//    2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.
//    a.왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
//    b.왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
//    c.네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
//    d.네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.
    
    
    for(int i = 0; i<4; i++){       //왼쪽부터 반시계방향
        
        int nd = (d+3-i)%4;
        int nr = r + dr[nd];
        int nc = c + dc[nd];
        
        if(nr<0 || nr>=N || nc<0 || nc>=M || map[nr][nc]==1) {  //범위 넘어가거나 벽이면 다음 방향
            continue;
        }
        
        //a.  아직 청소하지 않은 공간이 존재한다면
        if(visited[nr][nc] == 0 && map[nr][nc] == 0){
               visited[nr][nc] = 1; //현재 위치 청소
               dfs(nr, nc, nd, sum+1);
           }

    }
    

    int backIdx = d+2<4 ? d+2 : d-2;
    int backr = r + dr[backIdx];
    int backc = c + dc[backIdx];
    if(0<=backr && backr<=N && 0<=backc && backc<=M){
        if(map[backr][backc]==0){   //뒤쪽 방햑 벽 아니어서 후진할 수 있을 때
            dfs(backr, backc, d, sum);  //한칸 후진
        }
        else{   //뒤쪽 방향 벽이라 후진 못할 때
            cout << sum <<endl;
            exit(0);
        }
    }
      
}



int main(){
    
    int r, c, d;
    cin >> N >> M;
    cin >> r >> c >> d;
    
    for(int i = 0; i<N; i++){
        for(int j = 0; j<M; j++){
            cin >>map[i][j];
            visited[i][j] = 0;
        }
    }
    
    visited[r][c] = 1;
    dfs(r,c,d,1);

    return 0;
}

문제 링크 : www.acmicpc.net/problem/14889

문제

오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.

BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.

N=4이고, S가 아래와 같은 경우를 살펴보자.

i\j12341234

예를 들어, 1, 2번이 스타트 팀, 3, 4번이 링크 팀에 속한 경우에 두 팀의 능력치는 아래와 같다.

• 스타트 팀: S12 + S21 = 1 + 4 = 5
• 링크 팀: S34 + S43 = 2 + 5 = 7

1, 3번이 스타트 팀, 2, 4번이 링크 팀에 속하면, 두 팀의 능력치는 아래와 같다.

• 스타트 팀: S13 + S31 = 2 + 7 = 9
• 링크 팀: S24 + S42 = 6 + 4 = 10

축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다. 위의 예제와 같은 경우에는 1, 4번이 스타트 팀, 2, 3번 팀이 링크 팀에 속하면 스타트 팀의 능력치는 6, 링크 팀의 능력치는 6이 되어서 차이가 0이 되고 이 값이 최소이다.

입력

첫째 줄에 N(4 ≤ N ≤ 20, N은 짝수)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.

출력

첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다.

접근 방법

sumFunc이 DFS이다. 

DFS 돌면서 각각 팀의 능력치를 더한다.

그 능력치의 차를 구해서 최소가 되는 경우를 찾는다.

#include <iostream>
#include <vector>
#include <string.h>
#include <algorithm>

using namespace std;

int N;
int map[21][21];
int visited[21] = {0};
int num;

vector<int> start;
vector<int> link;

int chk[11] = {0};

vector<int> vec;
vector<int> sumVec;
int ans1 = 0;
int ans2= 0;
int ans = 100000000;


vector<int> sSum;

//DFS 돌면서 팀의 능력치 더함
void sumFunc(int toPick, vector<int> vec){
    
    if(toPick==0){
        
        int sum =  map[sumVec[0]][sumVec[1]] + map[sumVec[1]][sumVec[0]];
        sSum.push_back(sum);
        return;
    }
    
    for(int i = 0; i<vec.size(); i++){
        if(chk[i] ==0){
            chk[i] = 1;
            sumVec.push_back(vec[i]);
            sumFunc(toPick-1, vec);
            sumVec.pop_back();
            chk[i] = 0;
            
        }
    }
    
    
}


void choiceFunc(int toPick, int num){
    
    
    if(toPick==0){
        ans1 = 0; ans2 = 0;
        link.clear();
		
        //스타트와 링크 각각 start, link 벡터에 나눔
        for(int j = 1; j<=N; j++){
            if(visited[j]==0) {
                link.push_back(j);
            }
        }

        //스타트
        sumFunc(2, start);
        for(int i = 0; i<sSum.size(); i++){
            ans1+=sSum[i];
        }
        sSum.clear();
        
        //링크
        sumFunc(2, link);
        for(int i = 0; i<sSum.size(); i++){
            ans2+=sSum[i];
        }
        sSum.clear();


        if(ans1<ans2){		//더 큰게 ans1이 되게 바꿈
            int tmp=ans1;
            ans1=ans2;
            ans2=tmp;
        }
        
        if(ans1-ans2 < ans){ans = ans1-ans2;}	//능력치 차가 최소인 것 구함 
        memset(chk, 0, sizeof(chk));
        
        return;
        
    }
    
    for(int i = 1; i<=N; i++){
        
        if(visited[i]==0 && num<i){
            visited[i] = 1;
            start.push_back(i);
            choiceFunc(toPick-1, i);
            start.pop_back();
            visited[i] = 0;
            
        }
    }
    
}



int main(){
    
    cin >> N;
    for(int i = 1; i<=N; i++){
        for(int j = 1; j<=N; j++){
            cin >> map[i][j];
        }
    }

    num = (N*(N-1)) / 4;
    
    choiceFunc(N/2, 0);
    
    cout << ans/2 ;
    
    return 0;
}