SWEA - D4~D6(2)

SWEA 문제풀이

1. 전기버스2

   def sol(a):
       global cnt, result
       if a >= n:
           if result > cnt:
               result = cnt
           return
       if result < cnt:
           return
       b = a
       c = arr[b]
   
       for i in range(b+c, b, -1):
           cnt += 1
           sol(i)
           cnt -= 1
   
   for t in range(int(input())):
       arr = list(map(int, input().split()))
       n = arr[0]
       result = 987654321
       cnt = 0
       sol(1)
       print(f"#{t+1} {result-1}")

2. 최소생산비용

   def sol(a, s):
       global result
       if a == n:
           if result > s:
               result = s
           return
       if result < s:
           return
       for i in range(n):
           if visit[i] == 0:
               visit[i] = 1
               sol(a+1, s + arr[a][i])
               visit[i] = 0
   
   for t in range(int(input())):
       n = int(input())
       arr = [list(map(int, input().split()))for _ in range(n)]
       result = 1111111111111
       visit = [0] * n
       sol(0,0)
       print(f"#{t+1} {result}")

3. 연산

   from collections import deque
   
   def sol(start, end):
       check = {}
       check[start] = end
       while q:
           num, cnt = q.popleft()
           if num == end:
               return cnt
           if num > 1000000 or num <= 0:
               continue
           for i in range(4):
               a = 0
               if i == 0:               
                   a = num + 1
                   if a not in check:
                       q.append((a, cnt+1))
                       check[a] = 1
               elif i == 1:
                   a = num - 1
                   if a not in check:
                       q.append((a, cnt+1))
                       check[a] = 1
               elif i == 2:
                   a = num * 2
                   if a not in check:
                       q.append((a, cnt+1))
                       check[a] = 1
               elif i == 3:
                   a = num - 10
                   if a not in check:
                       q.append((a, cnt+1))
                       check[a] = 1
   
   for t in range(int(input())):
       n, m = map(int, input().split())
       q = deque()
       q.append([n, 0])    # 시작과 카운트 입력
       result = sol(n, m)
       print(f"#{t+1} {result}")

4. 그룹나누기

   def search(a):
       if a == group[a]:
           return a
       else:
           return search(group[a])
   def sol(a, b):
       group[search(b)] = search(a)
   
   for t in range(int(input())):
       n, m = map(int, input().split())
       arr = list(map(int, input().split()))
       group = []
       for i in range(1, n+1):
           group.append(i)
       group.insert(0,0)
       # print(group)
       for i in range(m):
           start = arr[2*i]
           end = arr[2*i+1]
           sol(start, end)
       result = []
       for i in range(len(group)):
           result.append(search(i))
       print(f"#{t+1} {len(set(result))-1}")

5. 최소 신장 트리

   def prim(a):
       key = [float('inf')for _ in range(v+1)]
       pi = [None for _ in range(v+1)]
       visit = [0 for _ in range(v+1)]
       key[0] = 0
       for _ in range(v+1):
           min_key =float('inf')
           start = -1
           for i in range(v+1):
               if key[i] < min_key and not visit[i]:
                   min_key = key[i]
                   start = i
           visit[start] = 1
           for V, W in a[start]:
               if W < key[V] and not visit[V]:
                   key[V] = W
                   pi[V] = start
       return sum(key)
   
   for t in range(int(input())):
       v, e = map(int, input().split())
       graph = {}
       for _ in range(e):
           n1, n2, weight = map(int, input().split())
           if n1 not in graph:
               graph[n1] = set()
           if n2 not in graph:
               graph[n2] = set()
           graph[n1].add((n2, weight))
           graph[n2].add((n1, weight))
       print(f"#{t+1} {prim(graph)}")

6. 최소 이동 거리

   def dis():
       key = [float('inf')for _ in range(n+1)]
       visit = [0 for _ in range(n+1)]
       check = set()
       check.add(0)
       key[0] = 0
       while True:
           min_key = float('inf')
           s = -1
           for i in check:
               if key[i] < min_key:
                   min_key = key[i]
                   s = i
           visit[s] = 1
           check.remove(s)
           if s == n:
               return key[s]
           for e, w in l[s]:
               if key[e] > key[s] + w and not visit[e]:
                   key[e] = key[s] + w
                   check.add(e)
   
   for t in range(int(input())):
       n, e = map(int, input().split())
       l = {}
    for _ in range(e):
           s, e, w = map(int, input().split())
           if s not in l:
               l[s] = [(e, w)]
           else:
               l[s] += [(e, w)]
       result = dis()
       print(f"#{t+1} {result}")

7. 7829 보물왕 태혁

   #include <stdio.h>
   
   int main(void) {
       int test_case;
       scanf("%d", &test_case);
       for (int t = 1; t <= test_case; t++){
           int n, x;
           int max = -1, min = 100001;
           scanf("%d", &n);
           for (int i = 0; i < n; i++) {
               scanf("%d", &x);
               if (max < x) {
                   max = x;
               }
               if (min > x) {
                   min = x;
               }
           }
           printf("#%d %d\n", t, min * max);
       }
       return 0;
   }

8. 괄호 짝짓기

   #include <stdio.h>
   
   char arr[100001];
   int n;
   bool solution(char* a, int* length) {
       int l = *length;
       if (a[l] == ')') {
           if (a[l - 1] == '(') {
               a[l - 1] = NULL;
               a[l] = NULL;
               *length -= 2;
               return true;
           }
           else return false;
       }
       if (a[l] == ']') {
           if (a[l - 1] == '[') {
               a[l - 1] = NULL;
               a[l] = NULL;
               *length -= 2;
               return true;
           }
           else return false;
       }
       if (a[l] == '}') {
           if (a[l - 1] == '{') {
               a[l - 1] = NULL;
               a[l] = NULL;
               *length -= 2;
               return true;
           }
           else return false;
       }
       if (a[l] == '>') {
           if (a[l - 1] == '<') {
               a[l - 1] = NULL;
               a[l] = NULL;
               *length -= 2;
               return true;
           }
           else return false;
       }
       return true;
   }
   
   int main() {
       for (int t = 1; t <= 10; t++) {
           int result = 1;
           int length = 0;
           scanf("%d", &n);
           for (int i = 1; i <= n; i++) {
               length++;
               scanf(" %1c", &arr[length]);
               if (solution(arr, &length) == false) {
                   result = 0;
               }
           }
           printf("#%d %d\n", t, result);
       }
   }

• 공통조상

  def sol(n):
      q = [n]
      cnt =0
      while q:
          cnt += 1
          a = q.pop()
          for i in v_1[a]:
              q.append(i)
      return cnt
  
  for t in range(int(input())):
      v, e, n1, n2 = map(int, input().split())
      n3 = 9**9
      v_1 = [[]for _ in range(v+1)]
      v_2 = [[]for _ in range(v+1)]
      data = [*map(int, input().split())]
      for i in range(e):
          v_1[data[2*i]].append(data[2*i+1])
          v_2[data[2*i+1]].append(data[2*i])
  
      while n1 != n3:
          n1 = v_2[n1][0]
          n3 = n2
          while n3>1 and n1 != n3:
              n3=v_2[n3][0]
      result = sol(n1)
      print(f"#{t+1} {n1} {result}")