dfs,bfs 관련 문제 풀고 익숙해지기
백준 - 바이러스
- 연결정보 파악
- 방문 체크 할 리스트 필요
- dfs 알고리즘
def dfs(start):
visited[start]=True
#start랑 연결되어 있는 컴퓨터 중에서
for i in connect[start]:
#방문 안했으면 그 컴퓨터를 시작으로해서 확인(점점 깊게)
if visited[i]==False:
dfs(i)
computers=int(input())
pair=int(input())
n=0
connect=[[]*computers for _ in range(computers+1)]
#바이러스의 방문여부 체크
visited=[False]*(computers+1)
for i in range(pair):
x,y=map(int,input().split())
#양방향 연결이니까
connect[x].append(y)
connect[y].append(x)
#1번 컴퓨터가 감염 됐을 경우
dfs(1)
#방문 했다 = 감염 됨
for virus in visited:
if(virus):
n+=1
#자기자신(1번 컴퓨터) 제외하고
print(n-1)
백준 - 단지번호붙이기
bfs 필요한거
1. 방문할 곳 저장해둘 공간(deque()이용)
2. 방문했는지 아닌지 check -> 방문한 곳을 또 방문할 필요없으니 전체 appartment에 표시해도 됨
from collections import deque
count=[]
def bfs(appartment,i,j):
n=len(appartment)
dx=[0,0,1,-1]
dy=[1,-1,0,0]
# 방문할 곳
visited=deque()
visited.append([i,j])
appartment[i][j]=0
count=1
while visited:
x,y=visited.popleft()
# 상하좌우
for pos in range(4):
nx=dx[pos]+x
ny=dy[pos]+y
# 범위 외
if nx<0 or nx>=n or ny<0 or ny>=n:
continue
# 단지번호 안 붙였으면 확인
if appartment[nx][ny]==1:
appartment[nx][ny]=0
visited.append([nx,ny])
# 번호 붙인거 갯수
count+=1
return count
N=int(input())
appartment=[]
for i in range(N):
appartment.append(list(map(int,input())))
for i in range(N):
for j in range(N):
if appartment[i][j]==1:
count.append(bfs(appartment,i,j))
# 오름차순으로 정렬
count.sort()
print(len(count))
for c in count:
print(c)백준 - 보물섬
단지 번호 붙이기랑 다른점
- 육지에서 육지까지의 거리를 각 시작점마다 구해야하므로 map에 방문여부 표시하면 안됨
- 시작점이 다를 때마다 visited를 초기화해서 방문한거 기록하기
from collections import deque
def bfs(map,i,j,h,w):
# 방문했는지 아닌지
visited=[[0]*w for _ in range(h)]
dx=[0,0,1,-1]
dy=[1,-1,0,0]
# 방문해야할 곳 queue에 저장
queue=deque()
queue.append((i,j,0))
visited[i][j]=1
distance=0
while queue:
x,y,d=queue.popleft()
for pos in range(4):
nx=dx[pos]+x
ny=dy[pos]+y
if nx>=h or nx<0 or ny>=w or ny<0:
continue
#방문도 안했고 육지일 때만
if map[nx][ny]=='L' and visited[nx][ny]==0:
visited[nx][ny]=1
# 한 칸 이동할 때마다 거리+1
queue.append((nx,ny,d+1))
distance=d+1
# 거리
return distance
h,w=map(int,input().split())
distance=[]
map=[]
for i in range(h):
map.append(list(input()))
for i in range(h):
for j in range(w):
# 시작점이 (i,j)일 때
if map[i][j]=='L':
distance.append(bfs(map,i,j,h,w))
print(max(distance))- 백준에서 python3로 돌리면 시간초과 뜨고, PyPy3로 돌려야 시간초과가 안뜸(python3로도 가능한 방법)
PyPy3는 JIT(just in time) 컴파일, 자주 쓰이는 코드를 캐싱하기 때문에 인터 프리터의 느린 실행속도를 개선할 수 있다고 한다.
- 더 자세한 내용은 pypy3 vs python2 여기 참고
백준- 토마토
- 익은 토마토를 큐에 넣고 시작
- 익은 토마토는 또 다시 안 봐도 되니까 tomato 배열을 건들여도 됨
from collections import deque
#상하좌우
dx=[0,0,1,-1]
dy=[1,-1,0,0]
M,N=map(int,input().split())
# 익은 토마토
queue=deque()
def bfs(tomato):
#토마토 익는데 걸리는 시간
date=0
while queue:
x,y,day=queue.popleft()
#상하좌우 토마토만
for pos in range(4):
nx=x+dx[pos]
ny=y+dy[pos]
if nx>=N or nx<0 or ny>=M or ny<0:
continue
#안 익은 토마토
if tomato[nx][ny]==0:
#익음
tomato[nx][ny]=1
#익은 토마토와 걸린 시간
queue.append((nx,ny,day+1))
date=day+1
return date
tomato=[]
#입력
for i in range(N):
tomato.append(list(map(int,input().split())))
for i in range(N):
for j in range(M):
#익은 토마토부터 시작하니까
if tomato[i][j]==1:
queue.append((i,j,0))
ans=bfs(tomato)
#안 익은 토마토가 있으면 실패(-1)
for i in range(N):
for j in range(M):
if tomato[i][j]==0:
ans=-1
break
print(ans)
백준-nQueen
대표적인 백트래킹 문제(백트래킹?)
퀸 N개를 서로 공격할 수 없게 놓는 문제
-> 퀸이 있는 방향의 상하좌우 대각선에는 또 다른 퀸이 없어야함.
N=int(input())
cnt=0
def dfs(queenPos,curCol):
global cnt
#같은 col에 있으면 안됨
if curCol in queenPos:
return
#지금 확인하고 있는 row
curRow=len(queenPos)
#대각선에 있는지 확인
for row,col in enumerate(queenPos):
#대각선에 있는지 확인
if abs(row-curRow)==abs(col-curCol):
return
#대각선에 없으면
queenPos.append(curCol)
#퀸을 다 자리에 놓았으면 방법+1
if len(queenPos)==N:
cnt+=1
#다음 퀸 자리에 앉히기
for col in range(N):
dfs(queenPos[:],col)
#맨 처음 퀸의 위치
for start in range(N):
queenPos=[] # idx=row, value=column
dfs(queenPos,start)
print(cnt)PyPy3로만 돌아감
전역변수 안쓰고 싶은데
안쓰려면
cnt=0을 cnt=[0]으로 바꾸고 cnt+=1을 cnt[0]+=1로 바꾼 다음에 cnt[0]을 출력하면 됨
전역변수,배열
참고
매일매일 성장하기 : )