본문 바로가기

Coding test

 (123)
[백준/15649/파이썬]N과M(1) - 백트래킹 소스코드 (permutations) from itertools import permutations n,m = map(int,input().split()) n_list = [i+1 for i in range(n)] ans = list(permutations(n_list, m)) for i in ans: print(' '.join(map(str, i))) 알고리즘 파이썬에 있는 permutations를 이용하면서 풀면 끝 ~ 이라는 생각으로 풀었다.근데 다른 사람들은 어떻게 풀었는지 검색을 해보니 백트래킹 기법을 이용하여 풀었다고 해서 뭐시여,,,하고 다시 풀어봤다. 소스코드 (backtracking) def dfs(): if len(s) == m: print(' '.join(map(str, s))) ret..
[백준/1655/파이썬]가운데를 말해요 소스코드 import sys import heapq input = sys.stdin.readline n = int(input()) max_h, min_h = [], [] for i in range(n): num = int(input()) if len(max_h) == len(min_h): heapq.heappush(max_h, -num) else: heapq.heappush(min_h, num) if len(max_h) >= 1 and len(min_h) >= 1 and max_h[0] * -1 > min_h[0]: max_value = heapq.heappop(max_h) * -1 min_value = heapq.heappop(min_h) heapq.heappush(max_h, min_value * -..
[백준/5014/파이썬] 스타트링크 소스코드 from collections import deque F,S,G,U,D = map(int,input().split()) def bfs(start): queue = deque([start]) visited[start] = 1 # 처음시작한 층수를 1로 해줘야 재방문 안함 while queue : start = queue.popleft() if start == G: # 목표 도달 return count[G] for i in (start+U, start-D): if (0 visited[6] = 1 count[6]=5 ) 즉 5층까지 가는데 4번 방문을 했어야하면 다음층은 5번 방문하면 된다는 소리이다. 방문안한 층수에 대해 queue에 삽입해나가며 실행하면 된다.
[백준/1697/파이썬] 숨바꼭질 소스코드 import sys from collections import deque input = sys.stdin.readline() def bfs(): q = deque() q.append(n) while q: x = q.popleft() if x == k: print(dist[x]) break for j in (x-1,x+1,x*2): if 0
[백준/2667/파이썬] 단지번호붙이기 소스코드 from collections import deque N = int(input()) graph = [] for i in range(N): graph.append(list(map(int, input()))) def bfs(graph,x,y): dx = [-1,1,0,0] dy = [0,0,-1,1] queue = deque() queue.append((x,y)) graph[x][y] = 0 cnt = 1 while (queue) : x,y = queue.popleft() for i in range (4): ax = x + dx[i] ay = y + dy[i] if (ax = N) or (ay =N): continue if graph[ax][ay] == 1: graph[ax][ay] = 0 queu..
[백준/2606/파이썬] 바이러스 소스코드 from collections import deque N = int(input()) M = int(input()) queue = deque() queue.append(1) computer = [] visited = [] for _ in range(M): a, b = map(int,input().split()) computer.append([a,b]) while (queue): virus = queue.popleft() if virus not in visited: visited.append(virus) for i in range (M): if virus == computer[i][0]: queue.append(computer[i][1]) elif virus == computer[i][1]: que..
[백준/2178/파이썬] 미로탐색 소스코드 from collections import deque N, M = map(int, input().split()) graph = [] for _ in range(N): graph.append(list(map(int, input()))) def bfs(x, y): dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] queue = deque() queue.append((x, y)) while queue: x, y = queue.popleft() for i in range(4): nx = x + dx[i] ny = y + dy[i] if nx = N or ny = M: # 위치가 벗어나면 안됨 continue if graph[nx][ny] == 0: # 벽은 이동 X continue i..
[백준/2644/파이썬] 촌수계산 소스코드 N = int(input()) A, B = map(int, input().split()) M = int(input()) graph = [[] for _ in range(N+1)] visited = [False] * (N+1) result = [0] * (N+1) for _ in range(M): x, y = map(int, input().split()) graph[x].append(y) graph[y].append(x) def dfs(v): visited[v] = True for i in graph[v]: if not visited[i]: result[i] = result[v] + 1 dfs(i) dfs(A) if result[B]>0: print(result[B]) else: print(-1)..

티스토리툴바