코뚫하 :: 2021 동계 모각코 1회차 결과

21.01.04. (월) 20시 ~ 23시

문다연
그래프 이론의 BFS, DFS의 알고리즘을 공부하고 이해하는 공부를 했다. 그래프 알고리즘의 가장 기본적인 코딩 문제를 해결하였다.
BOJ 1260 : DFS와 BFS, 2178 : 미로탐색

문혜림
『결과』

• 파이썬 설치 및 변수와 출력함수 학습

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;
		}
	}
}

2. 다익스트라 + 역추적 응용 문제
   https://www.acmicpc.net/problem/11779
   일반적으로 재귀 또는 스택을 이용하여 역추적을 하는거같았으나, 백트래킹 알고리즘이나 재귀 쪽으로 공부한 알고리즘이 별로 없어서 그래프를 뒤집고 최단경로와 일치하는 노드인지 확인하고 저장해주었다.
   그래프 알고리즘하는 도중 백트래킹과 재귀 알고리즘도 알아보아야겠다는 생각이 들었다.

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;
		}
	}
}

유정균
백준 15649 N과 M (백트래킹)
문제는 단순하다 1부터N까지의수 중에 길이가 M인 순열들을 차레대로 출력해주면된다
일단 어떻게 풀어야 할지 생각을 해보았다 머리로는 생각이 어느정도 되도
코딩을 어떻게 해야할지 막막했다
처음 생각한방법은 배열을 출력할 숫자의 칸만큼 만들어서 순열을 차례대로 넣고
배열을 출력하는것이었다 (예를들어 "4 2" 를 입력하면 가로의 길이가 2 세로가 4P2 만큼)
차례대로 넣기위해 내가생각한 방법은 한줄씩(가로)말고 한열씩(세로) 넣기로했다
만약 4 4를 입력하면 총 24줄이 나오고 그중 6줄 (24/4 = 6) 은 1로시작할것이다
그럼 이것들을 1~4의범위에서 6개씩 1열의 위에서부터 넣는다
2열도 같은방법으로 1열에 나오지않은숫자들을 2줄(6/3) ...... 같은방법으로하면
모두채울수있을것같았다 그러나 백트래킹이 아닌것같아서 포기하고 생각해보다가
구글링을했다.
백트래킹은 조건을 충족할때 맞는길로 계속가다가 충족하지않을때 뒤로가서 다른길로가는것이다
재귀를 사용해서 푼것을 보았다 처음에는 이해가 잘 되지않았지만 계속읽어보니 이해가됬다
내가 방법을 생각해내진 못해서 비슷한 문제를 풀어보면서 복습해야겠다.

자바잡기술++
내가모르던 재귀함수의 사용방법
함수가 여러번 호출될때 return; 을 사용해서 끝낼수있음
for each문

문다연 https://github.com/dayo2n/MGK_winter_2020/projects/1#card-52292050
문혜림 https://github.com/moo-nerim/20_Winter-Mogakco/blob/main/Lecture_01.py
박형기 https://blog.naver.com/qkrgudrl0324/222196320985
유정균 https://blog.naver.com/kyun1229/222196442135