bfs 송아지 이후부터 반복적으로 복습 필요
for i in range(3):
res[i]+=aa[x]
dfs(x+1)
res[i]-=aa[x] #호출해주고 다시 빼줘야 다른 줄기에서 계산될 때 정상 동작 가능
if __name__=='__main__' :
cnt=0
a=list(map(int, str(input())))
aa=len(a)
res=[0]*(aa+1)
dfs(0)
print(cnt)
==>
if __name__=="__main__":
code=list(map(int, input()))
n=len(code)
code.insert(n, -1)#이 부분을 꼭 추가해줘야 한다
res=[0]*(n+3) ```
cnt=0
DFS(0, 0)
print(cnt)
BFS파트 공부가 너무 미흡하게 돼있음. 꼼꼼히 집중적으로 복습하고 오답하기
for i in (k-1,k+1,k+5): #경우의 수가 세개뿐이므로 돌려주기
if 0<i<=maxi: #범위의 좌표안에 있는지 체크 필요
if ch[i]==0: #체크 안돼있는 애라면
ch[i]=1 #체크해주구
q.append(i) #큐에 넣어주구
dis[i]=dis[k]+1 #거리는 처음애보다 1더하기
=>전체 :
max=10000
ch=[0]*(max+1)
dis=[0]*(max+1)
n,m=map(int, input().split())
ch[n]=1
dis[n]=0
dq=deque()
dq.append(n)
while dq :
now=dq.popleft()
if now==m :
break
for next in(now-1, now+1, now+5) :
if 0<next<=max:
if ch[next]==0:
dq.append(next)
ch[next]=1
dis[next]=dis[now]+1
print(dis[m])
while True :
if level==n//2:
break
size=len(q)
for i in range(size) :
k=q.popleft()
for i in range(4) :
x=k[0]+dx[i]
y=k[1]+dy[i]
if ch[x][y]==0:
ch[x][y]=a[x][y]
q.append((x,y))
마지막으로 for i in range(size) 구문이 끝나서 q가 아예 다 갈아엎어지면 그때서야 level+=1 해준다
=>
dx=[-1,0,1,0]
dy=[0,1,0,-1]
n=int(input())
a=[list(map(int, input().split())) for _ in range(n)]
ch=[[0]*n for _ in range(n)]
ch[n//2][n//2]=1
sum=0
sum+=a[n//2][n//2]
q=deque()
q.append((n//2,n//2))
#k[0]이 앞의 값 k[1]이 뒤의 값
level=0
while True :
if level==n//2:
break
size=len(q)
for i in range(size) :
k=q.popleft()
for j in range(4):
x=k[0]+dx[j]
y=k[1]+dy[j]
if ch[x][y]==0:
sum+=a[x][y]
ch[x][y]=1
q.append((x,y))
print(level, size) #요 print 부분을 통해 어떻게 진행되고 있는지 살펴보자면
for i in ch :
print(i)
level+=1
from collections import deque
dx=[-1, 0, 1, 0]
dy=[0, 1, 0, -1]
a=[list(map(int, input().split())) for _ in range(7)]
ch=[[0]*7 for _ in range(7)] #몇번째 방문인 지 확인해주는 애
Q=deque()
Q.append((0, 0))
a[0][0]=1 #처음 출발값에 1 넣어줌으로써 벽처리 해준 것
while Q:
tmp=Q.popleft()
for i in range(4):
x=tmp[0]+dx[i]
y=tmp[1]+dy[i]
if 0<=x<=6 and 0<=y<=6 and a[x][y]==0: #x,y 둘다 0부터 6사이 범위에 있어야 하고 벽이 아니어야 하므로
a[x][y]=1 #이제 왔으면 얘는 벽으로 처리해줘야 함
ch[x][y]=ch[tmp[0]][tmp[1]]+1 #몇번째에 방문했는지 갱신
Q.append((x, y))
if ch[6][6]==0: # [6][6]이 끝난 뒤에도 그대로 0이라면 못왔다는 얘기
print(-1)
else:
print(ch[6][6])
dx=[-1,0,1,0]
dy=[0,1,0,-1]
def dfs(x,y) :
global cnt
if x==6 and y==6:
cnt+=1
else :
for i in range(4):
xx=x+dx[i]
yy=y+dy[i]
if 0<=xx<=6 and 0<=yy<=6 and a[xx][yy]==0:
a[xx][yy]=1
dfs(xx,yy)
a[xx][yy]=0 # 그 대신 벽 만들어주었던 거 호출한 뒤에는 원상복귀해주기
if __name__=='__main__' :
a=[list(map(int,input().split())) for _ in range(7)]
cnt=0
a[0][0]=1
dfs(0,0)
print(cnt)
dfs는 ch만드는 경우 거의 필요하지 않음, 최단 거리 구할때나 ch써서 갔던데 못가게 하는 것임
def dfs(x,y):
global cnt
if x==max1 and y==max2:
cnt+=1
return
else :
max=0
for i in range(4) :
xx=x+dx[i]
yy=y+dy[i]
if 0<=xx<=n-1 and 0<=yy<=n-1 and a[xx][yy]>a[x][y]:
dfs(xx,yy)
if __name__=='__main__' :
n=int(input())
a=[list(map(int,input().split())) for _ in range(n)]
max=-1 #목적지
min=101 #출발지
for i in range(n):
for j in range(n):
if a[i][j] > max:
max=a[i][j]
max1=i
max2=j
if a[i][j]<min:
min=a[i][j]
min1=i
min2=j
cnt=0
dx=[-1,0,1,0]
dy=[0,1,0,-1]
dfs(min1,min2)
print(cnt)
(1) DFS
dx=[-1, 0, 1, 0]
dy=[0, 1, 0, -1]
def dfs(x, y):
global cnt
cnt+=1 #하나가 넘어오면 카운트 시작 일단
a[x][y]=0
for i in range(4) :
xx=x+dx[i]
yy=y+dy[i]
if 0<=xx<=n-1 and 0<=yy<=n-1 and a[xx][yy]==1:
dfs(xx,yy)
if __name__=="__main__":
res=[]
n=int(input())
a=[list(map(int, input())) for _ in range(n)]
for i in range(n):
for j in range(n):
if a[i][j]==1:
cnt=0 #여기서 초기화를 해줬어야 한다! 단지마다 세는 것이니깐
dfs(i,j)
res.append(cnt) #res에 cnt더해주는 것 여기서 하기
res.sort()
print(len(res))
for i in res:
print(i)
(2) BFS
from collections import deque
q=deque()
res=[]
dx=[-1,0,1,0]
dy=[0,-1,0,1]
n=int(input())
a=[list(map(int,input())) for _ in range(n)]
for i in range(n) :
for j in range(n):
if a[i][j]==1:
a[i][j]=0
cnt=1
q.append((i,j))
while q:
k=q.popleft()
for i in range(4) :
xx=k[0]+dx[i]
yy=k[1]+dy[i]
if 0<=xx<n and 0<=yy<n and a[xx][yy]==1 :
cnt+=1
a[xx][yy]=0
q.append((xx,yy))
res.append(cnt)
print(len(res))
for i in res:
print(i)
(1)bfs
from collections import deque
dx=[-1,0,1,0]
dy=[0,1,0,-1]
n=int(input())
a=[(list(map(int, input().split()))) for _ in range(n)]
res=[] #개수 append 해놓고 마지막에 max값 꺼내주기
mini=min(map(min,a))
maxi=max(map(max,a))
q=deque()
for i in range(mini,maxi+1):
ch=[[0]*n for _ in range(n)] #물높이가 바뀔 때마다 초기화 해줘야 함
cnt=0
for j in range(n) :
for k in range(n) :
if a[j][k]>i and ch[j][k]==0:
ch[j][k]=1
q.append((j,k))
while q:
k=q.popleft()
for s in range(4):
x=k[0]+dx[s]
y=k[1]+dy[s]
if 0<=x<=n-1 and 0<=y<=n-1 and a[x][y]>i and ch[x][y]==0:
ch[x][y]=1
q.append((x,y))
cnt+=1
if cnt>0:
res.append(cnt)
print(max(res))
(2) dfs
dx=[-1, 0, 1, 0]
dy=[0, 1, 0, -1]
def dfs(x, y):
global cnt
cnt+=1 #하나가 넘어오면 카운트 시작 일단
a[x][y]=0
for i in range(4) :
xx=x+dx[i]
yy=y+dy[i]
if 0<=xx<=n-1 and 0<=yy<=n-1 and a[xx][yy]==1:
dfs(xx,yy)
if __name__=="__main__":
res=[]
n=int(input())
a=[list(map(int, input())) for _ in range(n)]
for i in range(n):
for j in range(n):
if a[i][j]==1:
cnt=0 #여기서 초기화를 해줬어야 한다! 단지마다 세는 것이니깐
dfs(i,j)
res.append(cnt) #res에 cnt더해주는 것 여기서 하기
res.sort()
print(len(res))
for i in res:
print(i)
from collections import deque
m,n = map(int,input().split()) #m이 열 n이 행
a=[list(map(int,input().split())) for _ in range(n)]
dx=[-1,0,1,0]
dy=[0,1,0,-1]
q=deque()
for i in range(n) :
for j in range(m) :
if a[i][j]==1:
q.append((i,j,0))
while q:
k=q.popleft()
for i in range(4) :
xx=k[0]+dx[i]
yy=k[1]+dy[i]
if 0<=xx<n and 0<=yy<m and a[xx][yy]==0:
a[xx][yy]=1
kk=k[2]+1
q.append((xx,yy,kk))
print(kk)
def dfs(x,s):
if x==m:
for x in cb:
print(x,end='')
print()
else :
for i in range(s,len(pz)) :
cb[x]=i
dfs(x+1,i+1)
if __name__=='__main__' :
pz=[]
hs=[]
n,m=map(int,input().split())
cb=[0]*m #n개중 m개뽑는 경우의 수 담아줄 공간
a=[list(map(int,input().split())) for _ in range(n)]
for i in range(n) :
for j in range(n) :
if a[i][j]==1:
hs.append((i,j))
elif a[i][j]==2:
pz.append((i,j))
dfs(0,0)
def dfs(x,y):
if x==0:
print(y)
else :
if y-1>=0 and a[x][y-1]==1 and ch[x][y-1]==0:
ch[x][y-1]=1
dfs(x,y-1)
elif y+1<10 and a[x][y+1]==1 and ch[x][y+1]==0:
ch[x][y+1]=1
dfs(x,y+1)
else :
ch[x-1][y]=1
dfs(x-1,y)
if __name__=='__main__' :
a=[list(map(int, input().split())) for _ in range(10)]
ch=[[0]*10 for _ in range(10)]
for i in range(10) :
for j in range(10) :
if a[i][j]==2:
ch[i][j]=0
dfs(i,j)
(1) 우선 나올 수 있는 경우의 순서들 구하는 법
조합: dfs(x,s) - for i in range(s,끝숫자) - list[x]=i, dfs(x+1,i+1)
def dfs(x,s):
if x==m:
for x in cb:
print(x,end='')
print()
else :
for i in range(s,len(pz)) :
cb[x]=i
dfs(x+1,i+1)
if __name__=='__main__' :
pz=[]
hs=[]
n,m=map(int,input().split())
cb=[0]*m #n개중 m개뽑는 경우의 수 담아줄 공간
a=[list(map(int,input().split())) for _ in range(n)]
for i in range(n) :
for j in range(n) :
if a[i][j]==1:
hs.append((i,j))
elif a[i][j]==2:
pz.append((i,j))
dfs(0,0)
(2) 조합들 구하고
global res
sum=0 #도시와 피자의 거리 구할 곳
for k in hs:
dis=19999 #집에서 피자집까지의 최소거리 구하기 위해
for x in cb:
dis=(dis, abs(k[0]-pz[x][0]) + abs(k[1]-pz[x][1]))
sum+=dis
#도시에서 피잣집 거리의 합들(총 cb개 가지) =sum
#이 수많은 sum들에서 가장 피자집 거리가 최소인 애를 구해줘야 하니 res랑 비교해서 얻어내기
if sum<res:
res=sum
(3) 최종 풀이
def dfs(x,s):
if x==m:
global res
sum=0 #도시와 피자의 거리 구할 곳
for k in hs:
re=[]
dis=19999 #집에서 피자집까지의 최소거리 구하기 위해
for x in cb:
dis=min(dis, abs(k[0]-pz[x][0]) + abs(k[1]-pz[x][1]))
sum+=dis
#도시에서 피잣집 거리의 합들(총 cb개 가지) =sum
#이 수많은 sum들에서 가장 피자집 거리가 최소인 애를 구해줘야 하니
if sum<res:
res=sum
else :
for i in range(s,len(pz)) :
cb[x]=i
dfs(x+1,i+1)
if __name__=='__main__' :
pz=[]
hs=[]
res=10000 #조합들 중 가장 작은 거리를 내는 경우의 수를 찾기 위해
n,m=map(int,input().split())
cb=[0]*m #n개중 m개뽑는 경우의 수 담아줄 공간
a=[list(map(int,input().split())) for _ in range(n)]
for i in range(n) :
for j in range(n) :
if a[i][j]==1:
hs.append((i,j))
elif a[i][j]==2:
pz.append((i,j))
dfs(0,0)
print(res)
#병합정렬
def dsort(lt,rt) :
if lt<rt :
mid=(lt+rt)//2
dsort(lt,mid)
dsort(mid+1,rt)
#두갈래로 뻗고 난 후에야 자기 본연의 일을 해주는 것
p1=lt
p2=mid+1
tmp=[]
while p1<=mid and p2<=rt:
if arr[p1]<arr[p2]:
tmp.append(arr[p1])
p1+=1
else :
tmp.append(arr[p2])
p2+=1
#나머지 처리해주기
if p1<=mid : tmp=tmp+arr[p1:mid+1]
if p2<=rt : tmp=tmp+arr[p2:rt+1]
for i in range(len(tmp)) :
arr[lt+i]=tmp[i]
if __name__=='__main__' :
arr=[23,11,45,36,15,67,33,21]
print('before sort : ' , end='')
print(arr)
dsort(0,7) #divide sort의 약자, 분할한 다음에 정렬,0번부터 7번까지 정렬하라
print()
print('after sort : ', end='')
print(arr)
#dsort 함수는 lt부터 rt까지의 영역을 두개의 영역으로 나누는 작업
#자기 영역을 무조건 절반으로 나누고
if arr[i]<=pivot: #피봇보다 큰애는 그냥 넘어가는데 작은애 만나면
arr[i], arr[pos]=arr[pos], arr[i]#이와 같이 스와프 해주고, pos에 1을 더해준다
pos+=1
=> 그러다가 마지막엔 pos랑 arr(rt) (=pivot)의 값이랑 스와프 해준다
==>이렇게 하면 pivot을 기준으로 피봇보다 작은 건 왼쪽에, 큰 건 오른쪽으로 나뉜다
#병합정렬
#파티션 작업을 하고 계속 분할 들어가기
def qsort(lt,rt) :
if lt<rt :
pos=lt #0으로 하면 안됨,분할된 부분의 시작점
pivot=arr[rt] #그 영역의 맨 오른쪽 값, 9하면 안됨
for i in range(lt,rt):
if arr[i]<=pivot: #피봇보다 큰애는 그냥 넘어가는데 작은애 만나면
arr[i], arr[pos]=arr[pos], arr[i]#이와 같이 스와프 해주고, pos에 1을 더해준다
pos+=1
arr[rt], arr[pos]=arr[pos], arr[rt] #(둘이 값만 바꾼 것임)
#전체작업 했으니 이젠 분할 #pos가 축이므로 pos 기준으로 나누면서 전체에 qsort 적용해주기 (가운데)
qsort(lt, pos-1) #왼쪽 아이들
qsort(pos+1, rt) #오른쪽 자식
if __name__=='__main__' :
arr=[45,21,23,36,15,67,11,60,20,33]
print('before sort : ' , end='')
print(arr)
qsort(0,9)
print()
print('after sort : ', end='')
print(arr)