연구소
어떻게 푸는 문제인지 한참 고민했는데, 부르트 포스로 푸는 문제였다. 벽을 세울 수 있는 경우에 대해 모두 탐색하며 풀었다. 이때, 리스트를 복사해야할 일이 많았는데, 아래와 같은 방법으로 이차원 배열을 복사해서 활용했다.
tmp_lab = [lab[i][::] for i in range(n)]
CODE
from copy import deepcopy
from collections import deque as dq
import sys
read = sys.stdin.readline
sys.setrecursionlimit(1000000000)
n, m = map(int, read().split())
lab = list(list(map(int, read().split())) for _ in range(n))
two = []
not_zero = 3
for i in range(n):
for j in range(m):
if lab[i][j] == 1:
not_zero += 1
if lab[i][j] == 2:
two.append([i, j])
not_zero += 1
dx = [1, 0, 0, -1]
dy = [0, 1, -1, 0]
answer = 0
def BFS():
cnt = 0
tmp_lab = [lab[i][::] for i in range(n)]
tmp_two = dq(two[::])
while tmp_two:
a, b = tmp_two.popleft()
for x, y in zip(dx, dy):
ax, by = a+x, b+y
if 0 <= ax < n and 0 <= by < m and tmp_lab[ax][by] == 0:
tmp_lab[ax][by] = 2
cnt += 1
if answer > n*m-cnt-not_zero:
return 2147000000
tmp_two.append([ax, by])
return cnt
def WALL(a, b, cnt):
global answer
if cnt == 3:
safe = n*m-BFS()-not_zero
answer = max(answer, safe)
return
if a == n:
return
flag = 1
if lab[a][b] == 0:
lab[a][b] = 1
if b == m-1:
WALL(a+1, 0, cnt+1)
lab[a][b] = 0
WALL(a+1, 0, cnt)
else:
WALL(a, b+1, cnt+1)
lab[a][b] = 0
WALL(a, b+1, cnt)
else:
if b == m-1:
WALL(a+1, 0, cnt)
else:
WALL(a, b+1, cnt)
WALL(0, 0, 0)
print(answer)
가사 검색
프로그래머스 문제는 정말 오랜만에 푼 것 같다. 이 문제를 풀며 효율성 통과가 아무리 해도 되지 않아, 검색하다가 Trie자료구조에 대해 접하게 되었다. 어제 Trie자료구조를 익힌 후 오늘 활용해 봤다.
CODE
def solution(words, queries):
class Node(object):
def __init__(self,key,data=None):
self.key = key
self.data = {}
self.children = {}
class Trie(object):
def __init__(self):
self.head = Node(None)
def insert(self, string):
curr_node = self.head
length=len(string)
if length in curr_node.data:
curr_node.data[length]+=1
else:
curr_node.data[length]=1
for char in string:
if char not in curr_node.children:
curr_node.children[char]=Node(char)
curr_node = curr_node.children[char]
if length in curr_node.data:
curr_node.data[length]+=1
else:
curr_node.data[length]=1
def search(self, string,length):
curr_node = self.head
for char in string:
if char in curr_node.children:
curr_node = curr_node.children[char]
else:
return 0
if length in curr_node.data:
return curr_node.data[length]
else:
return 0
answer = []
words_left=Trie()
words_right=Trie()
for w in words:
words_right.insert(w)
words_left.insert(w[::-1])
for q in queries:
length=len(q)
left=True
if q[-1]=="?":
left=False
q=q.strip("?")
if left:
q=q[::-1]
answer.append(words_left.search(q,length))
else:
answer.append(words_right.search(q,length))
return answer
이분 그래프
이분 그래프의 개념에 대해 처음 접했다.
- 그래프의 모든 노드들을 양분했을 때, 같은 그룹에 있는 노드들 끼리는 연결되어있지 않은 그래프를 이분 그래프라고 한다고 한다!
각각의 노드를 1과 2로 정하며 탐색해 나갔다. 한 점에 1이 저장되어 있으면 다음으로 연결되는 점들에는 2를 저장하고, 한 점에 2가 저장되어 있으면 다음 점들은 1로 저장하며 진행한다. 그러다가, 이미 값이 저장된 점을 확인했을 때, 1이 들어가야 할 자리인데 2가 들어가있거나 혹은 그 반대라면, 이분그래프가 아니라는 뜻으로 해석할 수 있었다.
CODE
from collections import deque
import sys
read = sys.stdin.readline
def BFS(x):
point = deque([x])
if check[x] == 0:
check[x] = 1
else:
return True
flag = 1
while point and flag == 1:
a = point.popleft()
if a in bridge:
for b in bridge[a]:
if check[b] == 0:
if check[a] == 1:
check[b] = 2
else:
check[b] = 1
point.append(b)
elif check[a] == check[b]:
flag = 2
if flag == 2:
return False
else:
return True
for _ in range(int(read())):
v, e = map(int, read().split())
bridge = dict()
for _ in range(e):
a, b = map(int, read().split())
if a in bridge:
bridge[a].append(b)
else:
bridge[a] = [b]
if b in bridge:
bridge[b].append(a)
else:
bridge[b] = [a]
check = list(0 for _ in range(v+1))
for i in range(1, v+1):
if not BFS(i):
print("NO")
break
else:
print("YES")
풀어야 할 문제
- 스타트 택시🔥🔥
- 미네랄
- 아기 상어
- 전깃줄 -2
- 치즈🔥
- 소가 길을 건너간 이유