[Coding Test]/[백준]

[백준] 14502 파이썬(python) : 연구소 - (★)

14502번 : 연구소 빈칸에 벽을 3개 세워서 바이러스를 퍼지게 한 다음 가장 많은 빈칸이 남도록 해야한다. 1) 빈칸을 돌며 벽 3개를 세운다 -> n, m의 최댓값은 8이기 때문에 완전탐색으로 모든경우를 돌 수 있다. 그리고 벽 3개를 세워 나머지는 배제해야 하기에 백트래킹을 떠올린다. 2) 벽을 모두 세운 후 그 경우에 대해 바이러스를 전파시키는데 연결되어 있는 바로 이웃칸으로 전염될 수 있으니까 bfs를 사용한다. 다 전염시키고 나서 빈칸(0)의 개수를 센다. ==> 백트래킹 안에서 bfs를 호출한다. from collections import deque visit = [[0 for col in range(10)] for row in range(10) ] #1 dx = [ 0, 0, 1, -1 ..

[백준] 2206 파이썬(python) : 벽 부수고 이동하기 - (3중 리스트)

2206번 : 벽 부수고 이동하기 전 포스팅에서 풀었던 bfs문제(2178번 미로탐색)에 조건을 하나 더 추가한 문제이다. 지금의 나로선 새로운 조건을 추가한것을 구현하는데 상당히 어렵고 답을 이해하는것도 힘들었다. 더 정진하겠다. import sys from collections import deque n, m = map(int, sys.stdin.readline().split()) graph = [ list(map(int, sys.stdin.readline().strip())) for _ in range(n) ] #1 visited = [[ [0, 0] for _ in range(m) ] for _ in range(n) ] #2 visited[0][0][0] = 1 #3 dx = [ 0, 0, -1,..

[백준] 2178 파이썬(python) : 미로 탐색

2178번 : 미로 탐색 그래프이론 문제 중에서도 너비 우선 탐색을 하는 bfs문제다. 파이썬에서는 deque라이브러리를 import해와서 사용한다. 너비 우선 탐색에 대해서는 조만간 포스팅 해보겠다. 첫번째 풀이) from collections import deque n, m = map(int, input().split()) graph = [ list(map(int, input())) for _ in range(n) ] #1 d = [ (-1, 0), (1, 0), (0, -1), (0, 1) ] #2 q = deque() #3 q.append((0,0)) #4 def bfs(): while q: #5 x, y = q.popleft() #6 for i in range(4): #7 dx = x + d[i..

[백준] 15652 파이썬(python) : N과 M (4)

15652번 : N과 M (4) import sys n, m = map(int, sys.stdin.readline().split()) res = [] def backTracking(depth): #1 if depth == m: print(*res) return for i in range(1, n+1): #2 if res and res[-1] > i: continue res.append(i) backTracking(depth+1) #3 res.pop() backTracking(0) #2, 3 : index를 이전 원소와 같은 숫자로 시작하게 하기 위해 i+1이 아닌 i를 인수로 입력 다른풀이) import sys n, m = map(int, sys.stdin.readline().split()) res = ..

[백준] 15650 파이썬(python) : N과 M (2) - (combinations이용)

15650번 : N과 M (2)   n, m = map(int, input().split())answer = []def backTracking(index): if len(answer) == m: #1 print(" ".join(map(str, answer))) return for i in range(index, n+1): #2 if i not in answer: answer.append(i) backTracking(i+1) #3 answer.pop()backTracking(1) #4 15649번과 비슷한 문제다.#1 : stack의 길이가 입력값 m과 같아지면 스택의 원소들을 출력한다.#2,..

[백준] 14888 파이썬(python) : 연산자 끼워넣기 - (★)

14888번 : 연산자 끼워넣기 모든 값을 연산자를 넣고 구하는 방법으로 브루트포스와 백트래킹을 떠올릴 수 있다. 연산자는 +, -, x, / 이렇게 4가지가 전부이고 입력받는 수의 범위는 2