鼻を貫通:2021冬毛殻鼻1回結果

21.01.04. (月)20時~23時
文多燕
図論におけるBFS,DFSのアルゴリズムを学習し理解する.図アルゴリズムの最も基本的な符号化問題を解決した.
BOJ 1260:DFSとBFS;2178:迷宮へナビゲート
文慧琳
『結果』
学習

Pythonインストールと変数と出力関数

a=input("input number : ")
print(a)

a, b = input("input number : ").split()
print(type(a)) # str
print(a+b) # 23

(1)

a, b = input("input number : ").split()
a = int(a) # 2
b = int(b) # 3
print(a+b) # 5

##### (2) map() 사용하여 정수화
a, b = map(int,input("input number : ").split()) 
print(a+b)  
print(a-b) 
print(a*b) 
print(a/b) 
print(a//b) # 몫
print(a%b)  # 나머지
print(a**b) # 거듭제곱

薄型機
1.基礎多題を解いた
https://www.acmicpc.net/problem/1753

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;

public class Main {
	static ArrayList<ArrayList<Node>> list = new ArrayList<>(); //그래프

	public static void main(String[] args) throws IOException {
		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()); // 간선의 개수

		for (int i = 0; i < N + 1; i++) {
			ArrayList<Node> arr = new ArrayList<>();
			list.add(arr);
		}

		int INF = Integer.MAX_VALUE;

		int[] min = new int[N + 1]; // 최단경로를 저장해줄 배열

		Arrays.fill(min, Integer.MAX_VALUE); // int최댓값으로 초기화

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

		min[start] = 0; // 시작지점만 0으로 설정해준다

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			Node n = new Node(e, v); // 간선들을 입력받아 그래프에 저장
			list.get(s).add(n);
		}

		// 최단경로 탐색 시작

		Node s = new Node(start, 0); // 시작정점 생성
		Queue<Node> pq = new PriorityQueue<>();
		pq.add(s);

		while (!pq.isEmpty()) {
			Node poll = pq.remove();
			int e = poll.end;

			for (int i = 0; i < list.get(e).size(); i++) {
				Node index = list.get(e).get(i);

				if (min[index.end] > min[e] + index.value) { 
					// 기존 최단경로가 새로 들어온 경로보다 오래걸릴경우

					min[index.end] = min[e] + index.value;
					// 값을 업데이트 해준다

					Node push = new Node(index.end, min[index.end]);
					pq.add(push);
				}

			}
		}

		// 최단경로 탐색 끝

		// 출력 시작

		for (int i = 1; i < N + 1; i++) {
			// 경로가 없는 정점은 INF값으로 남아있다
			if (min[i] == INF) {
				System.out.println("INF");
			} else {
				System.out.println(min[i]);
			}

		}

		// 출력 끝
	}

	// 노드 클래스 생성
	// 짧은 거리부터 확인하기 위해 정렬해주었다
	private static class Node implements Comparable<Node> {
		int end;
		int value; 

		public Node(int e, int v) {
			end = e;
			value = v;
		}

		@Override
		public int compareTo(Main.Node o) {
			return value - o.value;
		}
	}
}

マルチ出口+逆追跡アプリケーションの問題
https://www.acmicpc.net/problem/11779
一般に,再帰的またはスタックを用いて逆追跡を行うようであるが,遡及的アルゴリズムや再帰的アルゴリズムはあまり学習されていないため,図形を反転させ,最短経路に一致するノードがあるかどうかをチェックし保存する.
グラフアルゴリズムを行う過程でbacktrackingと再帰アルゴリズムを理解すべきだと思います.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;

public class Main {
	static ArrayList<ArrayList<Node>> list = new ArrayList<>();
	static ArrayList<ArrayList<Node>> reverselist = new ArrayList<>();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());
		int M = Integer.parseInt(br.readLine());

		for (int i = 0; i < N + 1; i++) {
			ArrayList<Node> arr = new ArrayList<>();
			ArrayList<Node> arr2 = new ArrayList<>();
			list.add(arr);
			reverselist.add(arr2);
		}
		int[] min = new int[N + 1];

		Arrays.fill(min, Integer.MAX_VALUE);
		StringTokenizer st;
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			Node n = new Node(e, v);
			Node revn = new Node(s, v);
			reverselist.get(e).add(revn);
			list.get(s).add(n);
		}
		st = new StringTokenizer(br.readLine());
		int start = Integer.parseInt(st.nextToken());
		int end = Integer.parseInt(st.nextToken());
		min[start] = 0;

		Node s = new Node(start, 0);

		Queue<Node> pq = new PriorityQueue<>();
		pq.add(s);

		while (!pq.isEmpty()) {
			Node poll = pq.remove();
			int e = poll.end;

			for (int i = 0; i < list.get(e).size(); i++) {
				Node index = list.get(e).get(i);

				if (min[index.end] > min[e] + index.value) {

					min[index.end] = min[e] + index.value;

					Node push = new Node(index.end, min[index.end]);
					pq.add(push);
				}
			}
		}
		// 다익스트라 끝

		// 역추적 시작

		s = new Node(end, 0); // 끝 노드 부터 시작
		pq.add(s);

		int[] trace = new int[N + 1]; // 역추적 노드

		int count = 0; // 노드 개수

		while (!pq.isEmpty()) {
			Node poll = pq.poll();
			int to = poll.end;

			for (int i = 0; i < reverselist.get(to).size(); i++) {
				Node index = reverselist.get(to).get(i);

				if (min[index.end] == min[to] - index.value) {
					// 다음 도착 지점의 최단경로가, 이전 노드의 최단경로 - 현재 경로의 거리일 경우

					trace[count] = index.end; // 역추적 배열에 노드를 저장

					count++; // 노드 갯수 +1

					pq.add(index);

					break; // 한 노드를 찾았을경우, 더이상 찾지 않아도 되므로 반복문 종료
				}
			}
		}

		System.out.println(min[end]);
		System.out.println(count + 1);

		for (int i = count - 1; i >= 0; i--) {
			// 역추적 배열엔 끝부터 시작순으로 저장이 되어있다
			// 출력은 시작부터 끝으로 해야 하므로 뒤에서부터 출력해준다!
			System.out.print(trace[i] + " ");
		}
		System.out.print(end);
	}

	private static class Node implements Comparable<Node> {
		int end;
		int value;

		public Node(int e, int v) {
			end = e;
			value = v;
		}

		@Override
		public int compareTo(Main.Node o) {
			return value - o.value;
		}
	}
}

乳杆菌
バックエンドトラッキング
問題は簡単で、1からNまでの数字の中から、長さMのシーケンスを順番に出力すればよい.
どうすればいいか考えてみたが、頭の中では少し考えていたが.
どうやってコードすればいいか分からない
1つ目のアイデアは、数字の格子に沿って並べ、順番に並べることです.
出力アレイ(例えば「42」と入力すると横長が2で4 P 2に等しい)
順番に置くために、私が考えている方法は1行1行ではなく、1列に置くことです
4を入力すると24行あり、そのうち6行(24/4=6)は1で始まる
では、これらを1~4の範囲に入れ、6つごとに1列目の上から置きます.
2列目も同様に1列目に出ない数字を2行(6/3)に分けて…同じ方法で.
私はすべてのものを満たすことができると思いますが、これは背信ではないと思います.だから私はあきらめて、考えました.
グーグルゲームをしました
逆追跡は条件を満たす時に正しい道を歩き続け、満たさない時に別の道を後ろに進む
私は幽霊で解くものを見て、最初はよく理解していませんでしたが、ずっと読んでいて、分かりました.
方法が思いつかないので、似たような問題を復習してみます.

ジャワサーカス++
私が知らない再帰関数の使い方
関数が複数回呼び出されたときに返されます.使用可能終了
ドアごとに
文多燕
文慧琳https://github.com/dayo2n/MGK_winter_2020/projects/1#card-52292050
薄型機
乳杆菌https://github.com/moo-nerim/20_Winter-Mogakco/blob/main/Lecture_01.py