22년 1월 3주차 회고록 (스터디 자랑)

/** * 한 역에서 출발해서 계속 가면 다시 출발한 역으로 돌아올 수 있는 노선을 순환선. * A -> B -> A = 순환 X = 그냥 일자이다. * A -> B -> C -> A = 순환 O = 순환된다. */ public class Main { static boolean visited[], isCycle; static int N, distance[]; static Queue<Integer> q = new LinkedList<Integer>(); public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = null; StringBuilder sb = new StringBuilder(); N = Integer.parseInt(br.readLine()); visited = new boolean[N + 1]; //방문 기록 distance = new int[N + 1]; // 순환선까지의 거리 Arrays.fill(distance, - 1); // 거리 초기화 (순환선안에서는 0으로 표시되어야한다.) //역 세팅 ArrayList<Integer> adj[] = new ArrayList[N + 1]; for (int i = 1; i <= N; i++) { //N까지 넣어야 한다. adj[i] = new ArrayList<Integer>(); } //구간정보 입력 for (int i = 0; i < N; i++) { st = new StringTokenizer(br.readLine(), " "); int a = Integer.parseInt(st.nextToken()); int b = Integer.parseInt(st.nextToken()); adj[a].add(b); adj[b].add(a); } System.out.println(Arrays.toString(adj)); //역세팅 확인해보기 //경로에서 순환선 찾기 dfs(adj, 0, 1); //각 역과 순환선의 거리 구하기 bfs(adj); for (int i = 1; i <= N; i++) { sb.append(distance[i]).append(" "); } System.out.println(sb); } private static void bfs(ArrayList<Integer>[] adj) { int cnt = 1; //순환선 전부 돌면서 지선인것을 찾아 거리를 계산해야한다. while (!q.isEmpty()) { int len = q.size(); for (int i = 0; i < len; i++) { int tmp = q.poll(); //순환선의 연결된 구간을 탐색 for (int j : adj[tmp]) { //거리가 이미 구해진 역은 제외(순환선) if (distance[j] != -1) continue; //지선이면 거리만큼 + distance[j] = cnt; //지선을 찾았으니 지선의 연결된 역 큐에 추가 q.add(j); } } cnt++; // 순환선과의 거리 } } /** * * 1 - 2,3 * 2 - 1,3 * 3 - 4,2,1,5 * 4 - 3,6 * 5 - 3 * 6, 4 */ private static void dfs(ArrayList<Integer>[] adj, int prev, int curr) { //탐색하는 역 방문체크 visited[curr] = true; //연결된 역 구간 모두 탐색 for (int next : adj[curr]) { //직전 방문지가 아니면서 이미 방문한 곳에 도착 -> 순환역 if (visited[next] && next != prev) { // 순환참조 막는것. isCycle = true; distance[next] = 0; q.add(next); break; //순환이면 바로 종료 } else if (!visited[next]) { //방문하지 않은 역 탐색 -> prev를 현재역, curr을 next로 넘긴다. dfs(adj,curr,next); //사이클에 속하는 경우 if (isCycle) { //이미 사이클에 속한 곳을 만남 -> 사이클 전부 돌았따는 뜻 if (distance[next] == 0) { isCycle = false; } else { distance[next] = 0; q.add(next); } return; } } } } }

import numpy as np def solution(n, results): answer = 0 win_or_lose = np.identity(n) for result in results: winner = result[0]-1 loser = result[1]-1 win_or_lose[winner][loser] = 1 win_or_lose[loser][winner] = -1 for i in range(n): for j in range(n): for k in range(n): if j == k: win_or_lose[i][k] = win_or_lose[i][j] win_or_lose[k][i] = win_or_lose[j][i] elif i == j: win_or_lose[i][k] = win_or_lose[j][k] win_or_lose[k][i] = win_or_lose[k][j] elif i == k: win_or_lose[i][k] = 1 win_or_lose[k][i] = 1 else: if win_or_lose[i][j]==-1 and win_or_lose[j][k]==-1: win_or_lose[i][k] = -1 win_or_lose[k][i] = 1 elif win_or_lose[i][j]== 1 and win_or_lose[j][k]==1: win_or_lose[i][k] = 1 win_or_lose[k][i] = -1 # print(win_or_lose) for i in range(n): if sum(win_or_lose[i] != 0) == n: answer += 1 return answer print(solution(5, [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]))

그래프에대해 알지못해서 어떻게 접근해야하는지 몰랐습니다.

그래프 문제는 접근 방향 자체가 어려웠던 것 같다.

첫 번째로 문제를 머리로 푸는 방법을 생각하기도 어려웠고, 그것을 코드로 어떻게 구현해야 할지 생각하는 것도 어려웠다.

그래프 문제는 해결방법을 떠올리는 것 조차도 어려운 것 같습니다 ㅠ

그래프 알고리즘을 공부하면 그래프 문제가 나오더라도 당활하지 않을 수 있으니 그래프에 대해 더 공부하자!

뭔가 아닌 것 같아도 끝까지 구현해보고 방향을 트는 것이 좋을 수도 있겠다는 생각이 들었다.

그래프 문제는 일단 몇가지 알고리즘이 존재하는 것 같다. 플로이드 와샬, 다익스트라 등 먼저 그런 알고리즘을 공부하고 직접 코드로 작성해본 다음에 응용한 문제를 풀어야 할 것 같다.

시간을 정해놓고 안되면... 구글링을 해보자...

아는만큼 풀 수 있으니, 계속 공부해야겠습니. BFS와 DFS는 너무 자주 쓰이는거 같으니 확실히 익혀놓는게 좋을것 같습니다.

BFS나 DFS를 이용해서 문제를 푸는 것에 익숙하지 않아서 더 많은 문제를 풀어봐야할 것 같다.

사실 아직 내가 모든 문제를 풀 실력이 되지 않기 때문에 정말 오랫동안 고민해도 접근 방법조차 전혀 모르겠는 문제는 오히려 빠르게 풀이를 보고 공부하고 따라해보는게 도움이 될 것 같다. 그런 작업을 계속 반복해서 많이 하는 것도 중요한 공부가 될 것 같다.

알고리즘 특성 상 결국 풀지 못하면 한게 0이 되기 때문에 특정 시간을 정해놓고 풀지 않으면 약간 오기같은게 생기는데 조금 내려놓는 것도... 좋은 것같다..ㅠ