13-1. 특정 거리의 도시
n, m, k, x = map(int, input().split())
road = []
for _ in range(m):
a, b = map(int, input().split())
road.append((a,b))
# 단방향 그래프 생성
graph = [[] for _ in range(m+1)]
for [a,b] in road:
graph[a].append(b)
## 두번 거치는 길을 어떻게?
ch=[0]*(n+1)
for i in range(1, n+1):
#체크...- 정답
"""
특정 거리의 도시찾기
4 4 2 1
1 2
1 3
2 3
2 4
"""
from collections import deque
n, m, k, x = map(int, input().split())
# 단방향 그래프 생성
graph = [[] for _ in range(m+1)]
for _ in range(m):
a, b = map(int, input().split())
graph[a].append(b)
## 최단거리 초기화
distance = [-1]*(n+1)
distance[x]=0 #[-1, 0, -1, -1, -1]
## BFS
q = deque([x])
while q:
now = q.popleft() # 현재 노드 꺼내기
for nxt in graph[now]: # 해당 노드가 갈 수 있는 다음 노드들
if distance[nxt] == -1: # 방문하지 않았는지 여부 확인
distance[nxt] = distance[now]+1 # 거리 갱신
q.append(nxt)
check = False
for i in range(1, n+1): #1번 노드부터 탐색
if distance[i]==k: #주어진 k와 같은값 찾기
print(i)
check = True
if check == False:
print(-1)- 이어진 노드를 찾아서 어떻게 특정 거리를 구할지 감을 못잡음
체크변수를 활용해보려고 했으나 DFS를 보고있는 나색히 - 거리문제는 최대한 BFS를 떠올릴것.
- 시작값을0 초기화를 -1로 둔것을 생각못함
- 루트노드에서 연결된 자식노드에 방문여부 확인후 최초 방문일시 부모노드의 값에 +1로 누적값을 두어 최종적으로 k번째 거친 노드를 찾을 수 있음
- 마지막 출력부분도 생각못한점 바로 max를 활용해서 최대값을 구할생각을 해버림. check변수로 T,F 를 활용해 예외처리(-1)까지 활용한점 기억하기
13-2. 연구소
- 2를 기준으로 상하좌우 탐색후 1이 아닌 0일때 +=1을 하여 3이 되면 그래프 전체를 탐색해 0의 갯수를 구하기
- 구할때마다 max값을 비교하여 전체경우를 찾자...! 였으나 구현로직짤수록 미궁에 빠짐
"""
# 3개 카운트
# 전체탐색하여 2를 기준으로 상하좌우 살피기 1-> 넘어가기 , 0일경우 +=1 k-=1,
## 3개가 한정되어 있기때문에 경우의 수가 생김. 0개 셌을때 갯수가 많으면 다시 탐색...
- 다시 초기화 시키고 count 한다 -> max값 찾아야함...
"""
n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
k=3
def count_zero(n, m):
cnt = 0
for i in range(n):
for j in range(m):
if graph[i][j] == 0:
cnt += 1
return cnt
for i in range(n):
for j in range(m):
if graph[i][j]==2 and k>0:
for k in range(4):
nx = i+dx[k]
ny = j+dy[k]
if nx>0 and ny>0 and nx<n and ny<m and graph[nx][ny]==0:
graph[nx][ny]+=1
k-=1
elif k==0:
count_zero(n, m)- 정답
input = sys.stdin.readline
n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
temp = [[0]*m for _ in range(n)] #벽을 설치한 뒤의 맵 리스트
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
answer=0
def virus(x,y):
for i in range(4):
nx = x+dx[i]
ny = y+dy[i]
if nx>=0 and nx<n and ny >=0 and ny<m:
if temp[nx][ny]==0:
temp[nx][ny]=2
virus(nx,ny)
def get_score():
score = 0
for i in range(n):
for j in range(m):
if temp[i][j]==0:
score +=1
return score
# 깊이 우선 탐색(DFS)을 이용해 울타리를 설치하면서, 매 번 안전 영역의 크기 계산
def dfs(count):
global answer
# 울타리가 3개 설치된 경우
if count ==3:
for i in range(n):
for j in range(m):
temp[i][j] = graph[i][j]
# 각 바이러스의 위치에서 전파 진행
for i in range(n):
for j in range(m):
if temp[i][j] == 2:
virus(i, j)
# 안전 영역의 최대값 계산
answer = max(answer, get_score())
return
# 빈 공간에 울타리를 설치
for i in range(n):
for j in range(m):
if graph[i][j]==0:
graph[i][j]=1
count +=1
dfs(count)
graph[i][j]=0
count -=1
dfs(0)
print(answer)바이러스를 퍼트려보는것 까지는 생각을 못함
13-3. 경쟁적 전염
- 못품
"""
경쟁적 전염
3 3
1 0 2
0 0 0
3 0 0
2 3 2
"""
from collections import deque
n, k = map(int, input().split())
graph = []
data = []
for i in range(n):
graph.append(list(map(int, input().split()))) # 1 0 2
for j in range(n):
if graph[i][j]!=0:
## 바이러스 종류, 시간, 위치x, 위치y
# [(1, 0, 0, 0), (2, 0, 0, 2), (3, 0, 2, 0)]
data.append((graph[i][j], 0, i, j))
print(data)
data.sort()
q = deque(data)
print(q)
# 지난 시간, 바이러스 좌표 x, y
ts, tx, ty = map(int, input().split())
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
# BFS
while q:
virus, s, x, y = q.popleft()
if s == ts:
break
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<= nx and nx <n and 0<=ny and ny<n:
## 아직 방문하지 않은 위치라면, 그 위치에 바이러스 넣기
if graph[nx][ny]==0:
graph[nx][ny] = virus
q.append((virus, s+1, nx, ny))
print(graph[tx-1][ty-1])- 낮은 번호부터 증식함으로 큐에 낮은 바이러스의 번호부터 삽입해야함.
13-4. 괄호 변환
- 내코드
좀더 손대면 할수 있을것 같기도 한데 낡고지침....
from collections import deque
# 균형잡힌 괄호인지 확인
def isBalance(p):
if p.count('(') == p.count(')'):
return True
return False
# 올바른 괄호인지 확인
def isRight(p):
p = list(p)
deq = deque()
for c in p:
if c == ')':
if len(deq)==0:
return False
deq.popleft()
else:
deq.append(c)
print(deq)
if len(deq)>0:
return False
return True
def solution(p):
answer = ''
# 균형잡힌 문자열인지 확인
if isBalance(p):
if isRight(p):
return p
else:
# u, v 확인....
return answer
print(solution("(()())()"))
print(solution(")("))
# print(solution("()))((()"))- 정답
# "균형잡힌 괄호 문자열"의 인덱스 반환
def balanced_index(p):
count = 0 # 왼쪽 괄호의 개수
for i in range(len(p)):
if p[i] == '(':
count += 1
else:
count -= 1
if count == 0:
return i
# "올바른 괄호 문자열"인지 판단
def check_proper(p):
count = 0 # 왼쪽 괄호의 개수
for i in p:
if i == '(':
count += 1
else:
if count == 0: # 쌍이 맞지 않는 경우에 False 반환
return False
count -= 1
return True # 쌍이 맞는 경우에 True 반환
def solution(p):
answer = ''
if p == '':
return answer
index = balanced_index(p)
u = p[:index + 1]
v = p[index + 1:]
# "올바른 괄호 문자열"이면, v에 대해 함수를 수행한 결과를 붙여 반환
if check_proper(u):
answer = u + solution(v)
# "올바른 괄호 문자열"이 아니라면 아래의 과정을 수행
else:
answer = '('
answer += solution(v)
answer += ')'
u = list(u[1:-1]) # 첫 번째와 마지막 문자를 제거
for i in range(len(u)):
if u[i] == '(':
u[i] = ')'
else:
u[i] = '('
answer += "".join(u)
return answer13-5. 연산자 끼워넣기
- 에러
combination, product를 사용하려다가 막힘
연산자 조합만 따로 경우의 수를 모두 구해서 계산을 하려고 했으나 막힘
결국 DFS 탈출조건을 연산 수행n에 맞춰 return 구함
간과한 부분은 사용한 연산 수만큼 다시 값을 초기화 시켜야함
def DFS(v, sum):
global minv, maxv, plus, minus, double, divid
if v == n:
minv = min(minv, sum)
maxv = max(maxv, sum)
else:
if plus>0:
DFS(v+1, sum+num[v])
if minus>0:
DFS(v+1, sum-num[v])
if double>0:
DFS(v+1, sum*num[v])
if divid>0:
DFS(v+1, sum//num[v])
from itertools import combinations
n = int(input())
num = list(map(int, input().split()))
#tools = list(map(int, input().split()))
plus, minus, double, divid = map(int, input().split())
# 전체탐색으로 모든 경우를 구해야할것 같은디
minv = 1e9
maxv = -1e9
DFS(1, num[0])
print(minv)
print(maxv)- 정답
"""
연산자 끼워넣기
2
5 6
0 0 1 0
"""
def DFS(v, sum):
global minv, maxv, plus, minus, double, divid
if v == n:
minv = min(minv, sum)
maxv = max(maxv, sum)
else:
if plus>0:
plus-=1
DFS(v+1, sum+num[v])
plus+=1
if minus>0:
minus -=1
DFS(v+1, sum-num[v])
minus +=1
if double>0:
double -=1
DFS(v+1, sum*num[v])
double +=1
if divid>0:
divid -=1
DFS(v+1, sum//num[v])
divid+=1
from itertools import combinations
n = int(input())
num = list(map(int, input().split()))
#tools = list(map(int, input().split()))
plus, minus, double, divid = map(int, input().split())
# 전체탐색으로 모든 경우를 구해야할것 같은디
minv = 1e9
maxv = -1e9
DFS(1, num[0])
print(maxv)
print(minv)13-6. 감시 피하기
- 문제라고 생각했던 부분은 이전 치킨배달이나 연구소등의 문제를 제대로 복습하지 않았기 때문에 해당 문제가 비슷한 유형이라는것을 알아도 풀지 못했음.
- S를 찾아 해당 전체 열, 행부분에 T의 존재여부를 감시를 피하도록 해야함. 구현부분을 어떻게 접근해야할지 막혔다.
- DFS만 접근을 하려고 했는데 정답코드를 보고 BFS의 숙달이 필요함을 다시금 느낌... 하나만 사용하려고 생각하지 말고 사고를 넓히자
"""
5
X S X X T
T X S X X
X X X X X
X T X X X
X X T X X
"""
from collections import deque
import sys
input = sys.stdin.readline
n = int(input())
graph = [list(input().split()) for _ in range(n)]
dx,dy = [-1,1,0,0], [0,0,-1,1]
queue = deque()
check = False
def bfs():
visited = [[False]*n for _ in range(n)]
for i in range(n):
for j in range(n):
if graph[i][j] == 'T': # T를 발견할 경우 Q에 넣기
queue.append((i,j))
while queue:
x,y = queue.popleft()
for i in range(4):
temp_x, temp_y = x,y
while True:
nx = temp_x + dx[i]
ny = temp_y + dy[i]
if 0 <= nx < n and 0 <= ny < n: # 그래프 내에서
if graph[nx][ny] == 'X' and visited[nx][ny] == False: # 1. 빈공간X 면서 방문한적이 없으면 = 학생을 찾지 못하면
visited[nx][ny] = True # T
elif graph[nx][ny] == 'S': # 2. 학생 발견하면
return False # F
elif graph[nx][ny] == 'O': # 3. 벽 발견하면
break # 멈춤
temp_x, temp_y = nx,ny
else:
break
return True
# 벽 체크
def recursive(index):
global check
if index == 3:
if bfs():
check = True
return
# 그래프의 모든 X에 0(벽)을 3개 생성하여 확인하기
for i in range(n):
for j in range(n):
if graph[i][j] == 'X': # 빈공간이면
graph[i][j] = 'O' # 벽생성
recursive(index + 1) # 벽+=1
graph[i][j] = 'X' # 다시 초기화
recursive(0)
if check:
print("YES")
else:
print("NO")
- 모든 학생을 찾지 못하면 YES, 학생을 찾으면 NO를 출력해야함.
- 벽 3개를 세울 수 있음으로 완탐을 사용해 그래프의 모든 X에 0벽을 3개 세우는 경우를 찾는다.
- 해당 경우에 방문 여부를 살피기 위한 visited를 사용해 전체를 False로 둔다
- BFS: 위의 경우에서 그래프를 전체 탐색하여 T를 발견하면 Q에 넣는다.
- 찾은 선생님을 기준으로 4방향을 탐색하여 벽이 나타날때까지 전체를 탐색한다
- 학생을 발견하면 False, BFS가 전체 끝날때까지 발견하지 못하면 True를 반환한다.
참고한 정답코드 : https://wookcode.tistory.com/174
13-7. 인구 이동
이런 ch13에 나온 문제들은 익숙해질때까지 복습하고 풀어야 접근이 가능할것 같다. 변수활용에 대한 아이디어를 떠올리지 못함.
"""
N:땅크기, L-R:인구 차이 범위
2 20 50
50 30
20 40
"""
import sys
input = sys.stdin.readline
from collections import deque
n,l,r = map(int,input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
dx, dy = [0,0,1,-1], [1,-1,0,0]
def bfs(a,b):
q = deque()
temp = []
q.append((a,b))
temp.append((a,b)) # 국경선을 공유하고 있는 나라들의 좌표값 저장
while q:
x,y = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<=nx<n and 0<=ny<n and visited[nx][ny] == 0:
# 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 연다.
if l<=abs(graph[nx][ny]-graph[x][y])<=r:
visited[nx][ny] = 1
q.append((nx,ny))
temp.append((nx,ny))
print(temp)
return temp
result = 0
# 인구이동이 한번 돌때마다
while 1:
visited = [[0]*(n+1) for _ in range(n+1)] #방문여부 체크
flag = 0 # 1:국경선이 열림, 0:인구이동 없음
for i in range(n):
for j in range(n):
if visited[i][j] == 0: # 최초 방문일 경우
visited[i][j] = 1 # 체크
country = bfs(i,j)
# 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
if len(country) > 1:
flag = 1
# 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
number = sum([graph[x][y] for x, y in country]) // len(country)
for x,y in country: # temp에 저장된 나라들에 인구수를 저장한다.
graph[x][y] = number
# 연합을 해체하고, 모든 국경선을 닫는다.
if flag == 0:
break
result += 1
print(result)
- temp라는 리스트를 만들어서 국경선을 공유하고 있는 나라들의 좌표값을 넣는다
- 국경선이 열려있다면, flag를 1로 바꿔서 인구 이동이 시작됨을 표시한다.
- 국경을 공유하고 있는 모든 나라들의 합에서 국경을 공유하고 있는 나라들의 개수로 나눠준 뒤, 그 값을 국경을 공유하고 있는(temp에 넣어줬던) 나라들의 인구수에 넣는다.
- 더이상 인구이동이 일어나지 않으면 flag를 0으로 바꾸고, while문을 종료한다.
- while문이 한번 돌 때마다 ( 인구이동이 동시에 한번 일어날 때마다) result값을 1씩 더해준 뒤, while문이 종료되면 result 값을 출력한다.
참고한 정답코드 : https://resilient-923.tistory.com/353
13-8. 블록 이동하기
- 너무너뭄너무 어렵다
- board 외벽으로 1을 사용해 둘러싼 후 new_board로 예외 처리
- BFS 탐색으로 que를 사용하여 이동/회전 할수 있는 경우를
can_move에 저장하고 confirm으로 방문했던 경우인지 확인 - 방문하지 않았다면 넣을 때 이동수를 count를 1씩 추가해서 큐에 넣어준다.
- cur1이나 cur2가 (N,N)일 때 count를 return 한다.
- 회전하는 경우 가로방향일때는 위/아래에 1이 하나라도 있으면 해당 방향 회전이 불가능하고, 세로방향일때는 왼쪽/오른쪽에 1이 하나라도 있으면 해당 방향 회전이 불가능하다는 것을 이용하여 푼다.
def can_move(cur1, cur2, new_board):
Y, X = 0, 1
cand = []
# 평행이동
DELTAS = [(-1, 0), (1, 0), (0, 1), (0, -1)]
for dy, dx in DELTAS:
nxt1 = (cur1[Y] + dy, cur1[X] + dx)
nxt2 = (cur2[Y] + dy, cur2[X] + dx)
if new_board[nxt1[Y]][nxt1[X]] == 0 and new_board[nxt2[Y]][nxt2[X]] == 0:
cand.append((nxt1, nxt2))
# 회전
if cur1[Y] == cur2[Y]: # 1. 가로방향 일 때 == y좌표가 같을때
UP, DOWN = -1, 1
for d in [UP, DOWN]:
if new_board[cur1[Y]+d][cur1[X]] == 0 and new_board[cur2[Y]+d][cur2[X]] == 0: #위아래모두 0이면 회전 가능
cand.append((cur1, (cur1[Y] +d, cur1[X])))
cand.append((cur2, (cur2[Y] +d, cur2[X])))
else: # 2. 세로 방향 일 때 == x좌표가 같을때
LEFT, RIGHT = -1, 1
for d in [LEFT, RIGHT]:
if new_board[cur1[Y]][cur1[X ] +d] == 0 and new_board[cur2[Y]][cur2[X ] +d] == 0: #좌우모두 0이면 회전 가능
cand.append(((cur1[Y], cur1[X ] +d), cur1))
cand.append(((cur2[Y], cur2[X ] +d), cur2))
return cand
def solution(board):
# board 외벽 둘러싸기
N = len(board)
new_board = [[1] * (N +2) for _ in range(N +2)]
for i in range(N):
for j in range(N):
new_board[i+1][j+1] = board[i][j]
# 현재 좌표 위치 큐 삽입, 확인용 set
que = deque([((1, 1), (1, 2), 0)])
confirm = set([((1, 1), (1, 2))]) # 방문여부 확인
while que:
cur1, cur2, count = que.popleft()
if cur1 == (N, N) or cur2 == (N, N):
return count
for nxt in can_move(cur1, cur2, new_board):
if nxt not in confirm:
# print((nxt, count+1)) # (((2, 1), (2, 2)), 1)
# print((*nxt, count + 1)) # ((2, 1), (2, 2), 1)
que.append((*nxt, count+1))
confirm.add(nxt)
print(solution([[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]]))📍 파이썬의 Asterisk(*)
파이썬에서 Asterisk(*)는 다음과 같은 상황에서 사용되는데 크게 4가지의 경우가 있다.
- 곱셈 및 거듭제곱 연산으로 사용할 때
- 리스트형 컨테이너 타입의 데이터를 반복 확장하고자 할 때
- 가변인자 (Variadic Arguments)를 사용하고자 할 때
- 컨테이너 타입의 데이터를 Unpacking 할 때
컨테이너 타입의 데이터를 Unpacking 할 때
함수의 인자로써 사용하는게 아닌 리스트나 튜플 데이터를 다른 변수에 가변적으로 unpacking 하여 사용하는 형태
numbers = [1, 2, 3, 4, 5, 6] # unpacking의 좌변은 리스트 또는 튜플의 형태를 가져야하므로 단일 unpacking의 경우 *a가 아닌 *a,를 사용 *a, = numbers # a = [1, 2, 3, 4, 5, 6] *a, b = numbers # a = [1, 2, 3, 4, 5] # b = 6 a, *b, = numbers # a = 1 # b = [2, 3, 4, 5, 6] a, *b, c = numbers # a = 1 # b = [2, 3, 4, 5] # c = 6참고자료 : https://mingrammer.com/understanding-the-asterisk-of-python/
참고한 정답코드 : https://velog.io/@tjdud0123/블록-이동하기-2020-카카오-공채-python
개발기록