no image
구름톤 챌린지 4주 차 문제 17 학습 일기
https://goor.me/wDFSjuDNjzXTTqH4A ​ import java.io.*; import java.util.*; class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int N = Integer.parseInt(st.nextToken()); int M = Integer.parseInt(st.nextToken()); ArrayList arr = new ArrayList(); for(i..
2024.02.18
no image
백준 1436 영화감독 숌
어느 영화감독이 시리즈를 제작하는데, 흔하게 1,2편으로 표기하는 것이 싫다고 666이 들어간 자연수 순서대로 시리즈를 제작한다는 스토리이다. 초등학교 저학년 때 어디선가 보았던 '책상은 책상이다' 라는 단편이 기억난다. 주인공은 삶이 너무 지루하다며, 침대를 의자라고 부르고 의자를 시계라고 부르는 힙스터가 되버린다. 이런 기행을 계속하던 주인공이 원래 사물의 이름을 까먹게 되고 타인과 대화가 불가능한 수준에 다다르는 내용까진 기억이 나는데, 후에 잘못을 뉘우치고 다시 광명을 찾는지는 모르겠다. 만약 아니라면 초등학교 저학년에게는 꽤나 비극적인 내용이 아닐 수 없겠다. 아무튼 이 영화감독이나 책상은 책상이다의 주인공이나, 창의성 점수는 높게 주지만 적당히 할 필요가 있다. 나 또한 반골기질이 강한 사람이..
2024.02.18
no image
백준 1753 최단경로
유명한 문제. 우선순위 큐, 인접 리스트, 너비 우선 탐색, 다익스트라 등 공부한 것이 많은 문제였다. 그래프의 최단거리를 탐색하면 되는데 간선의 가중치가 존재한다. 다익스트라 과정 그림 못그림 위의 그림은 단방향 그래프이다 다익스트라는 거리에 대한 초기값을 무한대로 초기화 해놓는다. 1번을 탐색 시작 정점이라고 했을 때, 1번 정점을 방문처리를 해준다. 일반적인 bfs는 큐에 넣을 때 방문처리를 하는 경우가 많은데 다익스트라를 사용할 때는 큐에서 꺼낼 때 방문처리를 해줘야 한다(물론 visited 없이도 풀 수 있다) 기존 거리보다 짧은 최단거리가 나온다면 계속 거리를 갱신해줘야 하는데 큐에 넣을 때 방문 처리 해주면 갱신하지 못하는 경우가 발생한다. 1번에서 간선이 존재하는(자신 포함) 정점의 거리를..
2024.02.18
no image
백준 1074 Z C언어
#include int main(){ int a; scanf("%d", &a); int n = 2; for(int i = 1; i = 1){ if (y >= n/2 && x >= n/2) answer += n*n - (n/2)*(n/2); else if (y >= n/2 && x = n/2) answer += n*n - 3*(n/2)*(n/2); else if (y < n/2 && x < n/2) answer += n*n - 4*(n/2)*(n..
2024.02.18
no image
백준 숫자카드 2 java
6 3 2 10 10 10 -10 -10 7 3 10 9 -5 2 3 4 5 -10 위에는 가진 카드, 밑에는 랜덤한 정수 - 카드더미가 주어진다. 카드더미에 안에 카드 중 내가 몇장을 가지고 있는지 출력하는 문제이다. 위에 예시로 보았을 때 나는10카드 3장, 3과 -10이 2장 3한장을 가지고 있는 것이고 3 0 0 1 2 0 0 2 이렇게 출력이 되야 한다. lower bound = 하한선 = 정렬되어있는 배열에서 처음으로 key값 이상의 값이 나오는 index upper bound = 상한선 = key값이 초과한 값의 index upper bound - lower bound를 하면 중복된 값이 몇개 있는지 알 수 있다. 출처 : https://st-lab.tistory.com/267 만약 arra..
2024.02.18
no image
[C] 백준 9663번 N-Queen : 네이버 블로그
이전에 비슷한, 어쩌면 동일하다고도 할 수 있는 문제를 풀어본 적이 있어서 쉽게 접근할 수 있었다. 퀸을 N x N 체스판에서 서로 공격할 수 없게 배치하는 경우의 수를 출력하면 된다. 먼저 떠올렸던 것은 N x N이니까, 직관적으로 2차원 배열을 0으로 초기화 시킨 후 퀸이 있는 곳을 1로 바꾸는 방법이었는데, 좀 복잡하기도 하고, 해당 문제는 오히려 1차원 배열을 통한 풀이법이 정석처럼 여겨져서 1차원으로 했다. 2차원 배열처럼 직관적이진 않지만 확실히 간단해지긴 한다. 배열의 인덱스가 세로, 즉 체스판의 행으로 보고 배열의 값을 퀸이 있는 열로 보면 된다. 예를 들어 'arr[4] = 2' 라면 퀸이 4행의 2열에 있다는 의미이다. 그러므로 malloc을 통해 입력받은 N만큼 배열 크기를 할당해주면..
2024.02.18

 

import java.io.*;
import java.util.*;
class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		ArrayList<ArrayList<Integer>> arr = new ArrayList<>();
		for(int i =0; i <= N; i++){
			arr.add(new ArrayList<Integer>());
		}
		for(int i = 0; i < M; i++){
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			arr.get(a).add(b);
			arr.get(b).add(a);
		}
		Queue<Integer> q = new LinkedList<>();
		boolean []visited = new boolean[N+1];
		ArrayList<Node> ans = new ArrayList<>();
		
	
		for(int i = 0; i < N; i++){
			Double edge = 0.0;
			Node nd = new Node();
			if(arr.get(i).size() > 0 && !visited[i]){
				visited[i] = true;
				nd.nodeNum.add(i);
				for(int j = 0; j < arr.get(i).size(); j++){
					q.add(arr.get(i).get(j));
				}
				while (!q.isEmpty()){
					int nextNode = q.poll();
					edge++;
					if(!visited[nextNode]){
						visited[nextNode] = true;
						nd.nodeNum.add(nextNode);
						for(int j = 0; j < arr.get(nextNode).size(); j++){
							q.add(arr.get(nextNode).get(j));
						}
					}
				}
			nd.ans = edge / nd.nodeNum.size();
			ans.add(nd);
			}
		}
	
		for(int i = 0; i < ans.size(); i++)
			Collections.sort(ans.get(i).nodeNum);
		Collections.sort(ans, Node.customComparator);
		System.out.println(ans.get(0).ans);
		
		for(int i = 0; i <ans.get(0).nodeNum.size(); i++)
			System.out.print(ans.get(0).nodeNum.get(i) + " ");
	}
}


class Node{
    ArrayList<Integer> nodeNum = new ArrayList<>();
    Double ans;
	
    public static Comparator<Node> customComparator = new Comparator<Node>() {
        @Override
        public int compare(Node node1, Node node2) {
            // 1. ans가 가장 높은 것
            int ansComparison = Double.compare(node2.ans, node1.ans);
            if (ansComparison != 0) {
                return ansComparison;
            }

            // 2. ans가 같을 때 nodeNum의 인자갯수가 적은 것
            int numCountComparison = Integer.compare(node1.nodeNum.size(), node2.nodeNum.size());
            if (numCountComparison != 0) {
                return numCountComparison;
            }
					
            // 3. 2까지 같을 때는 nodeNum의 인자 중 가장 작은 인자가 있는 Node
            for (int i = 0; i < node1.nodeNum.size(); i++) {
                int numComparison = Integer.compare(node1.nodeNum.get(i), node2.nodeNum.get(i));
                if (numComparison != 0) {
                    return numComparison;
                }
            }

            return 0; // 모든 비교 기준이 같을 경우
        }
    };
}

 

쉽게 말하면 노드와 간선 수를 둘 다 구하면 된다.

근데 약간 꼼수 아닌 꼼수가 있다면, 실제는 양방향 간선으로 양 노드 간 간선 수를 하나로 세야 하지만,

그냥 각각 노드에서 간선의 수를 카운트 했기 때문에 2개로 치고 풀었다.

그래서 실제 밀도를 구하면 예시와는 다르지만 답은 맞는다.

그리고 밀도가 같을 때가 참 지저분한데, 그건 우리 형 gpt의 도움을 받아서 comparator의 compare 메소드를 오버라이드 해서 구현했다.

제시한 정답에서는 간선의 개수를 따로 세었는데. 난 그냥 탐색할 때 카운트 했다.

어느 영화감독이 시리즈를 제작하는데, 흔하게 1,2편으로 표기하는 것이 싫다고 666이 들어간 자연수 순서대로 시리즈를 제작한다는 스토리이다.
초등학교 저학년 때 어디선가 보았던 '책상은 책상이다' 라는 단편이 기억난다. 주인공은 삶이 너무 지루하다며, 침대를 의자라고 부르고 의자를 시계라고 부르는 힙스터가 되버린다. 이런 기행을 계속하던 주인공이 원래 사물의 이름을 까먹게 되고 타인과 대화가 불가능한 수준에 다다르는 내용까진 기억이 나는데, 후에 잘못을 뉘우치고 다시 광명을 찾는지는 모르겠다. 만약 아니라면 초등학교 저학년에게는 꽤나 비극적인 내용이 아닐 수 없겠다. 아무튼 이 영화감독이나 책상은 책상이다의 주인공이나, 창의성 점수는 높게 주지만 적당히 할 필요가 있다. 나 또한 반골기질이 강한 사람이지만, 기본적인 사회적 합의는 지키면서 사는 것이 좋겠다.
아무튼 이 영화감독이 정한 시리즈의 규칙은
1편 = 666
2편 = 1666
3편 = 2666
.
.
.
7편 = 6660
8편 = 6661
이런식이다
최적화 방법은 모르겠고, 카테고리도 '부르트 포스' 에 있기 때문에, 무식하고 미련한 방식으로 해결한다. 사실 일반적인 알고리즘 문제에서 이중 반복문 미만은 최적화에 크게 포커스를 둘 필요도 없을 것이다. 숫자를 666부터 1씩 더해가면서 '666'이 들어있으면 카운트를 해준다. 카운트와 입력받은 숫자가 일치하면 출력해주면 된다.
처음에는 int를 유지하면서 해결하려고 했다. 10으로 나눈 나머지가 숫자 6이면 수를 한번 세주고 아니면 0으로 초기화 해준다. 이렇게 하면 연속적으로 6이 있어야만 0으로 초기화 되지 않는데, 3까지 도달하면 그 수는 '666'이 포함됐다고 할 수 있겠다. 그렇게 제출해서 한번 틀리고 문자열로 치환해서 검사하면 훨씬 편할 것 같다는 생각을 했다.
1씩 더해주며 검사하는 것은 똑같지만, 문자열로 바꾸니 인덱스를 돌면 되니 훨씬 편했다. 인덱스를 돌다가 일단 '6'이 나오면, 이후에 두번 다 6이 나오는 지 체크했다.
#include <string.h>
#include <stdlib.h>
#include <stdio.h>

int beast_num_checker(char *beast_num)
{
    int i;

    i = 0;
    while (beast_num[i])
    {
        if (beast_num[i] && beast_num[i] == '6')
        {
            if (beast_num[i + 1] && beast_num[i+1] == '6')
            {
                if (beast_num[i+2] && beast_num[i+2] == '6')
                    return (1);
            }
        }
        i++;
    }
    return (0);
}


char *itoa(int a)
{
    int num;
    int cnt;
    char *itoa_num;

    num = a;
    cnt = 0;
    while (num != 0)
    {
        num /= 10;
        cnt++;
    }

    itoa_num = malloc(cnt + 1);
    itoa_num[cnt] = '0';
    cnt--;

    while (cnt >= 0)
    {
        itoa_num[cnt] = (a % 10) + '0';
        a /= 10;
        cnt--;
    }
    return (itoa_num);
}


int main()
{
    int a;
    int num;
    int cnt;
    int beast_num;
    
    beast_num = 666;
    cnt = 0;
    num = 0;
    while (1)
    {
        a = getc(stdin);
        if (a == 'n')
            break;
        num = num * 10 + (a - '0');
    }

    while (1)
    {
        if (beast_num_checker(itoa(beast_num)))
        {
            cnt++;
            if (cnt == num)
                break;
        }
        beast_num++;
    }
    printf("%d", beast_num);
}
구현은 위에 설명한 것이 다이고. 오히려 특이사항이 있다면, 최대한 로우레벨로 구현하기 위해 scanf를 사용하지 않은 것과 itoa 부분이다.
getc를 통해서 표준입력으로 부터 한글자씩 입력 받았다. getc함수는 문자의 아스키 코드를 int형으로 반환해주기 때문에, 1 은 49 2는 50으로 반환되는 식이다. 그래서 반환값에서 문자 '0' 즉 48을 빼줘야 진짜 int형으로 저장이 된다. 그리고 숫자를 입력 받을 때 마다 이전 숫자에 10을 곱한 후 더해주어서 10진수의 자릿수 연산을 해주었다. getc를 통해 읽어온 문자가 개행문자일 때 반복문 탈출 조건을 줬기 때문에, enter를 누르면 입력이 종료된다.
itoa 부분도 비슷한데, getc를 통해 받은 값을 0이 될때까지 10으로 나누어 보면서 자릿수를 체크하고 malloc을 통해 자릿수 +1 만큼 메모리를 할당해준다. 맨 마지막 인덱스에는 null문자를 넣어주고, 10의 나머지 연산을 통해 숫자를 문자열에 거꾸로 넣어준다.
num = 123 으로 치면 123을 10으로 나눈 나머지 3을 넣어주고, num에는 123 을 10으로 나눈 12로 초기화 해준다. 다시 12를 10으로 나눈 나머지 2를 넣어주고 앞의 과정을 반복해주면 된다. 나머지 연산을 활용하기 때문에 거꾸로 넣어줘야 한다.
문자열에 넣어줄 때는 아까 getc와는 반대로, 문자 '0' 만큼의 값을 더해줘서 문자열에 넣어줘야 숫자가 의미하는 문자로서 문자열에 넣어줄 수 있다.
유명한 문제.
우선순위 큐, 인접 리스트, 너비 우선 탐색, 다익스트라 등 공부한 것이 많은 문제였다.
그래프의 최단거리를 탐색하면 되는데 간선의 가중치가 존재한다.
다익스트라 과정
그림 못그림
위의 그림은 단방향 그래프이다
다익스트라는 거리에 대한 초기값을 무한대로 초기화 해놓는다.
1번을 탐색 시작 정점이라고 했을 때, 1번 정점을 방문처리를 해준다.
일반적인 bfs는 큐에 넣을 때 방문처리를 하는 경우가 많은데 다익스트라를 사용할 때는 큐에서 꺼낼 때 방문처리를 해줘야 한다(물론 visited 없이도 풀 수 있다)
기존 거리보다 짧은 최단거리가 나온다면 계속 거리를 갱신해줘야 하는데 큐에 넣을 때 방문 처리 해주면 갱신하지 못하는 경우가 발생한다.
1번에서 간선이 존재하는(자신 포함) 정점의 거리를 초기화 해주면서 우선순위 queue에 넣어줘서 다음 탐색에 방문할 후보로 넣어준다.
우선순위 큐는 node클래스의 거리를 비교하여 더 작은 거리를 가진 node가 나올 수 있게 했다.
방문노드 1
 
정점
1
2
3
4
5
거리
0
1
3
INF
INF
 
1에서 갈 수 있는 정점은 2와 3이고 그 둘의 거리가 1, 3으로 바꼈다. 거리 갱신은 현재 노드 + 간선
그리고 다음 탐색 노드를 정하는데, 탐색 시점 기준 거리가 가장 짧은 노드를 선택한다.
표를 기준으로는 2번 노드가 거리 1로 가장 짧기 때문에 2를 방문노드로 선정한다.
우선순위 큐를 사용한 이유인데, 그냥 꺼내면 거리가 가장 짧은 2번 node가 나오게 된다.
방문 노드 2
 
정점
1
2
3
4
5
거리
0
1
2
INF
5
 
2번 노드를 방문하고 앞선 과정을 반복해본다.
2번 노드를 현재 노드로 설정하고 방문처리 해준다.
2번에서 갈 수 있는 노드중에서 방문하지 않은 노드에 대해서 최소값을 비교해본다.
1은 2에서 갈 수 있지만 이미 방문했으니 초기화 되지 않는다.
1 -> 3으로 연결된 3의 비용을 지닌 간선보다 1->2의 거리인 1과 2->3의 거리인 1을 더한 2의 비용을 가진 루트가 더 짧은 것을 알게 된다.
그리고 2->4가 가능하니 4번 노드에 대한 거리가 2번노드 거리 1과 5번 노드 거리 4를 더한 5로 초기화 된다.
거리 배열은 아래와 같이 갱신된다.
방문 가능한 모든 노드를 큐에 넣어준다.
3번 노드도 다시 한번 큐에 들어가는데, 갱신된 거리와 함께 들어간다.
그러므로 지금 큐에 있는 노드를 (노드, 거리)로 작성하면
(3,2) (3, 3) (5, 5) 가 들어가 있을 것이다.
우선순위 큐를 통하면 2의 거리를 가진 3번 노드가 다음 방문 노드로 선정될것이다.
3번 노드를 방문 처리 해주고 탐색을 진행한다.
방문노드 3
 
정점
1
2
3
4
5
거리
0
1
2
6
3
 
같은 과정이니 짧게 설명하자면,
3에서 5번 노드로 가는 길이 이전 거리보다 짧기 때문에 갱신이 될 것이고, 4번 노드의 거리가 첫번째로 갱신이 된다.
큐에는 4번 5번 노드가 들어간다.
큐에는 이전에 들어가있던 (3, 3) (4, 5)와
(4, 6) (5, 3) 이 들어가서
(3, 3), (5, 3), (4, 5) (4, 6)이 들어가있다.
큐에서 값을 꺼내면 3의 거리를 가진 3번노드가 나올텐데 3번 노드는 이미 방문처리가 되어 있으므로 방문하지 않고
반복문을 통해 다시 값을 꺼내면 5번 노드가 나오게 된다.
5번노드는 방문할 수 있는 노드가 없으므로 다시 위의 과정을 반복하여 4번 노드가 나오고
4번 노드도 5번과 동일하게 조건문을 타지 않아서 결국 q.isEmpty = true가 되어 탐색이 끝나게 된다.
최종
 
정점
1
2
3
4
5
거리
0
1
2
6
3
 
내가 계속 실수했던 부분은, 갱신된 거리값을 가진 노드 객체를 큐에 넣어줘야 하는데, 간선값만을 지닌 객체를 넣어준 것이다.
그래서 오래걸렸다.

 

import java.util.*;
import java.io.*;


public class Main {
    static int nodeNum;
    static int[] distance;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        nodeNum = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());

        int startNode = Integer.parseInt(br.readLine());

        PriorityQueue<Node> q = new PriorityQueue<>();
        ArrayList<ArrayList<Node>> edge = new ArrayList<>();
        boolean[] visited = new boolean [nodeNum+1];
        distance = new int[nodeNum+1];

        for(int i = 1; i <= nodeNum; i++)
            distance[i] = Integer.MAX_VALUE;
        for(int i = 0; i <= nodeNum; i++)
            edge.add(new ArrayList<>());

        for(int i = 0; i < n; i++){
            st = new StringTokenizer(br.readLine());
            int w = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            edge.get(w).add(new Node(d, v));
        }
        q.add(new Node(startNode, 0));
        distance[startNode] = 0;
        Dijkstra(edge, distance, visited, q);
        for(int i = 1; i <= nodeNum; i++){
            if(!visited[i])
                System.out.println("INF");
            else
                System.out.println(distance[i]);
        }
    }

static void Dijkstra(ArrayList<ArrayList<Node>> edge, int[]distance, boolean[] visited, PriorityQueue<Node> q){

        while(!q.isEmpty()){        
            int node = q.poll().vertex;
            if(!visited[node]){
                visited[node] = true;
                for(int j = 1; j <= edge.get(node).size(); j++){
                    if(distance[node] + edge.get(node).get(j-1).value < distance[edge.get(node).get(j-1).vertex])
                        distance[edge.get(node).get(j-1).vertex] = distance[node] + edge.get(node).get(j-1).value;
                    q.add(new Node(edge.get(node).get(j-1).vertex, distance[edge.get(node).get(j-1).vertex]));
                }
            }
        }
    }
    
}

class Node implements Comparable<Node> {
    int vertex;
    int value;

    public Node(int d, int v) {
        this.vertex = d;
        this.value = v;
    }

    @Override
    public int compareTo(Node p) {
        return this.value - p.value;
    }
}
 

 

#include <stdio.h>

int main(){

    int a;
    scanf("%d", &a);

    int n = 2;

    for(int i = 1; i < a; i++)
        n *= 2;

    int y, x;
    scanf("%d", &y);
    scanf("%d", &x);

    int answer = 0;
    while(n >= 1){
        if (y >= n/2 && x >= n/2)
            answer += n*n - (n/2)*(n/2);
        else if (y >= n/2 && x < n/2)
            answer += n*n - 2*(n/2)*(n/2);
        else if (y < n/2 && x >= n/2)
            answer += n*n - 3*(n/2)*(n/2);
        else if (y < n/2 && x < n/2)
            answer += n*n - 4*(n/2)*(n/2);
        if (n == 1)
            break;
        y = y % (n/2);
        x = x % (n/2);
        n /= 2;
    }
    printf("%d", answer - 1);


}
간만에 C로 풀었다.
이거 어렵다.
발상이 정말 어렵다. 5시간 걸렸다.
핵심은 '분할'이다. 가장 큰 사각형부터 2X2 사각형까지 Z자로 연산이 계속된다는 점을 파악한 후,
사각형을 계속 4등분 하면서 적절한 연산을 해주면 되는데,
2차원 배열의 인덱스가 n/2의 값을 가지는 4등분 된 사각형 안에서 다시 어떤 인덱스를 가지는 지 생각하는 게 정말 어려웠다.
해답은 나머지 연산.
좌표에 대해서 n으로 나머지 연산을 시행하면
사각형을 분할했을 때 그 사각형을 기준으로 상대적인 좌표의 위치를 알 수 있다.
 
 
 
6 3 2 10 10 10 -10 -10 7 3
 
10 9 -5 2 3 4 5 -10
위에는 가진 카드, 밑에는 랜덤한 정수 - 카드더미가 주어진다.
카드더미에 안에 카드 중 내가 몇장을 가지고 있는지 출력하는 문제이다.
위에 예시로 보았을 때 나는10카드 3장, 3과 -10이 2장 3한장을 가지고 있는 것이고
3 0 0 1 2 0 0 2
이렇게 출력이 되야 한다.
lower bound = 하한선 = 정렬되어있는 배열에서 처음으로 key값 이상의 값이 나오는 index
upper bound = 상한선 = key값이 초과한 값의 index
upper bound - lower bound를 하면 중복된 값이 몇개 있는지 알 수 있다.
 
만약 array에 없는 값, 사진 기준으로 5라고 가정해보면
lower bound = 5
upper bound = 5
가 나오므로 둘의 차는 0이 되어 없다는 판정을 할 수 있다.
라고 했는데 이후에 무려 2시간을 더 써서 풀었다
추후 서술
이전에 비슷한, 어쩌면 동일하다고도 할 수 있는 문제를 풀어본 적이 있어서 쉽게 접근할 수 있었다.
퀸을 N x N 체스판에서 서로 공격할 수 없게 배치하는 경우의 수를 출력하면 된다.
먼저 떠올렸던 것은 N x N이니까, 직관적으로 2차원 배열을 0으로 초기화 시킨 후 퀸이 있는 곳을 1로 바꾸는 방법이었는데, 좀 복잡하기도 하고, 해당 문제는 오히려 1차원 배열을 통한 풀이법이 정석처럼 여겨져서 1차원으로 했다.
2차원 배열처럼 직관적이진 않지만 확실히 간단해지긴 한다. 배열의 인덱스가 세로, 즉 체스판의 행으로 보고 배열의 값을 퀸이 있는 열로 보면 된다. 예를 들어 'arr[4] = 2' 라면 퀸이 4행의 2열에 있다는 의미이다. 그러므로 malloc을 통해 입력받은 N만큼 배열 크기를 할당해주면 N x N의 정보를 모두 담을 수 있는 1차원 배열을 만들 수 있는 것이다.
문제 핵심은 백트래킹이다. 나는 아직 개념이 충분하진 않지만 해당 문제가 백트래킹의 대표적인 예제라고 한다. 내 이해를 말하자면 백트래킹은 모든 경우의 수를 탐색하여 답을 찾는 것이다. 조건에 따라 후보군을 탐색하며 유망(promising)한지 검사하고, 유망하다면 하위 깊이에서 또 탐색을 하고, 그렇지 않다면 더 하위로 가지 않고 가지치기(Pruning)를 하고 뒤로 돌아가서(Backtrack) 다음 후보군을 탐색한다. 그 과정에서 구조는 재귀를 활용하는데, 목표 깊이에 도달했을 때(배열이 다 채워졌을 때) 카운트를 ++해준 뒤 탈출조건을 설정해놓고 재귀를 돌리면 된다.
이제 서로 공격하지 못하게 배치하려면 퀸이 공격할 수 있는 루트를 생각해봐야 한다. 퀸은 가로와 세로, 대각선은 모두 움직일 수 있다. 때문에, 체스판을 2차원 배열로 보면 같은 열과 행은 당연히 위치할 수 없고, 대각선에 위치해서도 안된다.
1차원 배열에서는 인덱스 = 행 값 = 열 이기 때문에 일단 인덱스를 증가시키면서 반복문을 돌면 같은 행에는 위치할 수 없다. 그렇다면 같은 열에 있을때는 유망하지 않다는 조건을 써야하는데, 반복문을 돌면서 이전 1차원 배열에 저장되어 있는 값들과 비교하여 같은 값이 있다면 조건문을 false로 설정하면 된다.
대각선 조건은 수학적으로 조금 생각해보면 쉽게 풀린다. 정사각형 판에서 대각선의 의미는, 두 퀸을 직선으로 연결한 직선 즉, 1차원 그래프의 기울기가 1 (좌즉 대각선은 -1) 임을 의미한다. 때문에, y증가량 / x증가량 == 1, y증가량 == x증가량 이라면 대각선에 위치한다고 해석할 수 있는 것이다. 좌측 우측 모두 편하게 계산하기 위해 절대값을 씌운 후 동일한 지 조건문을 써줬다.
유망한 지 판별하는 조건
int is_Queen_valid(int nd, int i, int *arr) { 
int j = 0; 
while (j < nd) { 
	if (i == arr[j]) 
		return 0; 
	if(abs(nd - j) == abs(i - arr[j])) 
		return 0; j++; } return 1; 
}
소스코드
#include <stdio.h>
#include <stdlib.h>

int is_Queen_valid(int nd, int i, int *arr);
int abs(int a);
void queen(int *arr, int now_depth, int final_depth, int *cnt);


int abs(int a)
{
    if (a < 0)
        return (-1 * a);
    else
        return (a);
}

int is_Queen_valid(int nd, int i, int *arr)
{
    int j = 0;
        while (j < nd)
        {
            if (i == arr[j])
                return 0;
            if(abs(nd - j) == abs(i - arr[j]))
                return 0;
            j++;
        }
    return 1;
}

void queen(int *arr, int now_depth, int final_depth, int *cnt)
{
    int i = 0;
    int size = final_depth;
    if (now_depth == final_depth)
        {
            *cnt += 1;
            return ;
        }
    
    while (i < size)
        {
            if (is_Queen_valid(now_depth, i, arr))
            {
                arr[now_depth] = i;
                queen(arr, now_depth + 1, final_depth, cnt);
            }
        i++;
        }
}

int main()
{
    int a;
    scanf("%d", &a);
    int *arr = malloc(sizeof(int) * a);
    int cnt = 0;
    queen(arr, 0, a, &cnt);
    printf("%d", cnt);
    free(arr);
}
queen에서 파라미터로 받은 함수만 잘 살펴보면 된다.
arr = 체스판을 형상화한 1차원 배열
now_depth = 현재 탐색 깊이
final_depth = 목표 탐색 깊이
cnt = 방법의 수

'알고리즘-문제' 카테고리의 다른 글

구름톤 챌린지 4주 차 문제 17 학습 일기  (0) 2024.02.18
백준 1436 영화감독 숌  (0) 2024.02.18
백준 1753 최단경로  (0) 2024.02.18
백준 1074 Z C언어  (0) 2024.02.18
백준 숫자카드 2 java  (0) 2024.02.18