DFS

인접행렬이해

arr = [[0,1,1,0,0,0],
       [0,0,0,1,1,0],
       [0,0,0,0,0,1],
       [0,0,0,0,0,0],
       [0,0,0,0,0,0],
       [0,0,0,0,0,0],
        ]

n= input()
index = ord(n)-65
result = []
flag = 0
parent = -1
for i in range(6):
    if arr[i][index] == 1:
        parent = i
if parent == -1: print("형제 없음")
else:
    for j in range(6):
        if arr[parent][j] == 1 and j != index: #부모의 형제들을 리스트에 추가
            result.append(j)
            flag = 1

    if flag == 0:
        print('형제 없음')
        print(result)
    else:
        for m in result:
            print(chr(m+65))

DFS로 탐색하며 탐색하는 순서 출력하기

name=list(input().split())  # B A C D
arr=[
    [0,0,1,1],
    [1,0,0,0],
    [0,1,0,1],
    [0,0,0,0],
]
used=[0]*4
answer=[]
def dfs(now):
    global answer
    answer.append(name[now])
    for i in range(4):
        if arr[now][i]==1:
            if used[i]==0:
                used[i]=1
                dfs(i)
used[0]=1
dfs(0) # B 부터 깊이우선 탐색 시작
print(*answer)

한 정점에서 다른 정점까지 갈 수 있는 방법의 개수

**name=list(input().split())  # B A C D
arr=[
    [0,0,1,1],
    [1,0,1,0],
    [1,0,0,1],
    [0,0,0,0],
]
used=[0]*4
cnt=0
def dfs(now):
    global cnt
    if now==3:
        cnt+=1
    for i in range(4):
        if arr[now][i]==1 and used[i]==0:
            used[i]=1
            dfs(i)
            used[i]=0

used[1]=1
dfs(1)
print(cnt)**

출발점부터 도착지까지 갈 수 있는 방법의 개수

Q. 출발점을 입력 받습니다. 입력받은 출발점 알파벳부터 E가 써있는 곳 까지 갈 수 있는 방법이 몇가지 있는지 출력해주세요.(A입력 시 3가지, D입력 시 1가지, B입력 시 3가지)

name=['A','B','C','D','E']
st=input()
arr=[
    [0,1,0,0,0],
    [0,0,1,1,1],
    [1,0,0,1,0],
    [0,0,0,0,1],
    [0,0,0,0,0],
]
used=[0]*5
cnt=0
def dfs(now):
    global cnt
    if name[now]=='E':
        cnt+=1
    for i in range(5):
        if arr[now][i]==1 and used[i]==0:
            used[i]=1
            dfs(i)
            used[i]=0

st_index=0
for i in range(5):
    if name[i]==st:
        st_index=i
        break
used[st_index]=1
dfs(st_index)
print(cnt)

도착지점에 도달할 시 최소비용 구하기

name=['A','B','C','D','E']
st=input()  # 출발점 입력
arr=[
    [0,4,0,0,0],
    [0,0,1,2,9],
    [5,0,0,7,0],
    [0,0,0,0,1],
    [0,0,0,0,0],
]
used=[0]*5

Min=int(21e8)
def dfs(now,sum):
    global Min
    if name[now]=='E':
        # 최소 비용 (최소 sum)
        if sum<Min:
            Min=sum

    for i in range(5):
        if arr[now][i]>0:
            if used[i]==0:
                used[i]=1
                dfs(i,sum+arr[now][i])
                used[i]=0

# 출발점의 인덱스 확인
st_index=0
for i in range(5):
    if name[i]==st:
        st_index=i
        break

used[st_index]=1
dfs(st_index,0)
print(Min)

DFS 통한 최대값 구하기

arr=[
    [2,5,7],
    [8,4,-8],
    [-7,1,4],
    [5,1,9]
]
Max=int(-21e8)

def dfs(level, sum):
    global Max
    if level==4:
        if sum>Max:
            Max=sum
        return

    for i in range(3):
        dfs(level+1,sum+arr[level][i])

dfs(0,0) # level sum
print(Max)

술 취한 사람이 세 방향으로 이동할 수 있는데 최대값 구하기

def dfs(now,level,sum):
    global arr,MAX
    if level == 5:
        if MAX < sum:
            MAX = sum
        return 

    direct = [-1,0,1]
    for i in range(3):
        dy = level
        dx = now + direct[i]
        if dx < 0 or dx > 3:continue
        if arr[dy][dx] == 0:continue
        dfs(dx,level+1,sum+arr[dy][dx])
    
arr = [
    [3,2,4,1],
    [0,1,0,5],
    [2,0,3,0],
    [5,4,0,2],
    [2,-5,0,3]
]
MAX = 0
#첫 시작점 잡기
for i in range(4):
    dfs(i,0,0) 
print(MAX)

0은 길이고 1은 벽인데 이동 가능 출력