[7]알고리즘스터디 - 섹션7_3주차 스터디

파이썬 알고리즘 문제풀이 스터디 - 알까기 _ 섹션 7

 

 

 

 

 

티스토리 마크다운이 이상해서 올려놓은 깃허브 주소도 올린다.

 

https://github.com/dumi33/TIL_TodayILearn/blob/main/220225/%EC%84%B9%EC%85%987.md

GitHub - dumi33/TIL_TodayILearn: 오늘 배운 코드/내용을 정리해서 올립니다.

문제 1 - 최대점수 구하기(DFS)

• 내가 만든 코드
• 1, 2번은 잘 돌아가는데 나머지는 시간초과

def dfs(x,score, time) :
    global max_score
    if time>m : # 타임제한 초과
        return  # 해당 def 함수 끝냄 
    else :
        max_score = max(max_score,score)
        for i in range(n) :
            if ch[i]==0 : # 가지 않았다면 
                ch[i] = 1 # 갔음을 표시 
                dfs(i,score+graph[i][0],time+graph[i][1])
                ch[i] = 0

if __name__ == "__main__" :
    n,m = map(int,input().split())
    ch = [0] * (n+1) # 풀었던 문제 또 풀면 안되지 
    max_score = 0
    graph = [] # 튜플
    for _ in range(n) :
        s,t = map(int,input().split())
        graph.append((s,t))  # a에서 b를 갈 수 있다. # 이차원 배열 이란다
    dfs(0, 0, 0) # 0문제를 풀고, score는 0점이다. 지나간 시간은 0이다.
    print(max_score)

 

20220924

->이건 그냥 문제를 푸냐 안푸냐 2가지 밖에 없으니까 귀찮게 for문 돌리지말고, ch배열도 안만드는게 좋다.

그냥 dfs(), dfs() 이렇게 푸냐 , 안푸냐만 생각해서 풀어주는게 편하다. 강사님 코드 처럼 

 

 

- 강사님의 코드

def dfs(L,score, time) :
    global max_score 
    if time > m : # 제한시간 초과 
        return 
    if L == n : # 모든 문제를 지나갔을 때 # 이래서 cnt가 필요없음 
        if score >max_score : 
            max_score = score
    else :
        dfs(L+1,score+graph[L][0],time+graph[L][1]) # 문제를 풀었을 때
        dfs(L+1, score, time) # 문제를 풀지않았을 때 


if __name__ == "__main__" :
    n,m = map(int,input().split())
    max_score = 0
    graph = [] # 튜플
    for _ in range(n) :
        s,t = map(int,input().split())
        graph.append((s,t))  # a에서 b를 갈 수 있다. # 이차원 배열 이란다
    dfs(0, 0, 0) # 0문제를 풀고(level), score는 0점이다. 지나간 시간은 0이다.
    print(max_score)

문제 2 - 휴가(DFS)

• 내가 만든 코드
• 맞았다.

def dfs(L,money) :
    global max_money 
    if L > n : # 날이 n보다 커버리면 
        return 
    if L == n : # 모든 날이 지나갔을 때
        if money > max_money : 
            max_money = money
    else :
        dfs(L+graph[L][0],money+graph[L][1]) # 상담을 했을 때 
        dfs(L+1,money) # 상담을 하지않았을 때 


if __name__ == "__main__" :
    n= int(input())
    max_money = 0
    graph = [] 
    for _ in range(n) :
        d,m = map(int,input().split()) #  day : 소요 날짜, money
        graph.append((d,m))  # d만큼 시간이 소요되고, m 만큼 보수를 받는다.
    dfs(0, 0) # 0 카운슬러(level), money : 0점이다. 
    print(max_money)

- 강사님의 풀이

 def dfs(L,money) : # L은 날짜 
    global max_money 
    if L == n+1  : # 모든 날이 지나갔을 때
        if money > max_money : 
            max_money = money
    else :
        if L +graph[L][0] <= n+1 : 
            dfs(L+graph[L][0],money+graph[L][1]) # 상담을 했을 때 
        dfs(L+1,money) # 상담을 하지않았을 때 


if __name__ == "__main__" :
    n= int(input())
    max_money = 0
    graph = [] 
    for _ in range(n) :
        d,m = map(int,input().split()) #  day : 소요 날짜, money
        graph.append((d,m))  # d만큼 시간이 소요되고, m 만큼 보수를 받는다.
    graph.insert(0,[0,0]) # 인덱스를 맞추기위해서 
    dfs(1, 0) # 0 카운슬러(level), money : 0점이다. 
    print(max_money)

문제 3 - 양팔저울(DFS)

 def dfs(L,sum) :

    if L == k:
        if sum <= 0 or sum >s:
            return 
        else :
            res.add(sum)
    else :
        dfs(L+1, sum + nums[L])
        dfs(L+1, sum - nums[L])
        dfs(L+1, sum)


if __name__ == "__main__" :
    k = int(input()) # 추의 개수 
    nums =list((map(int,input().split()))) # 추의 무게 
    s = sum(nums)
    res = set() # 중복을 제거 
    dfs(0,0)
    print(s - len(res))

 

20220925의 코드 : (dictionary 사용) 근데 set을 사용하는게 더 좋을듯?

def dfs(idx,val) :
    if val not in dic and val >0 :
        dic[val] = 1 
    if idx == k : return 
    dfs(idx+1, val+mp[idx])
    dfs(idx+1, val-mp[idx])
    dfs(idx+1, val)
        
if __name__=="__main__" :
    k = int(input())
    mp = list(map(int,input().split()))
    dic = {}
    vis = [0]*3
    dfs(0,0)
    print(sum(mp) - len(dic))

 

 

 

문제 4 - 동전 바꿔주기 (DFS)

• 20220925 복습할 때도 못풀었다😓

동전의 개수대로 for문을 돌린다는 생각을 못하고 동전 하나하나 마다 vis배열을 만들었더니 중복이 엄청났다.

그래서 set을 생각해서 해봤는데도 잘못된 접근이었다. 정답은 for문을 동전의 개수만큼 도는 것이어따..!!!🐣

그러면 동전이 0개 들어갔을 때부터 모든 동전이 사용될 때 까지 모든 경우의 합의 값을 구할 수 있다. 

def dfs(L,sum) :
    global ans 
    if sum > t : return 
    if L==k :
        if sum == t : 
            ans+=1 
        return 
    for i in range(mp[L][1]+1) :
        dfs(L+1, sum+mp[L][0]*i)
        
if __name__=="__main__" :
    t = int(input())
    k = int(input())
    ans = 0
    mp = []
    for i in range(k) :
        a,b = map(int,input().split())
        mp.append([a,b]) 
    dfs(0,0) 
    
    print(ans)

 

 

문제 5 - 동전 분배하기 (DFS)

import sys
def dfs(L) :
    global ans 
    if L == N:
        tmp= max(person) - min(person)
        if tmp < ans :
            # 세 사람의 총액은 서로 달라야함 
            val = set()
            for x in person :
                val.add(x)
            if len(val) == 3 :
                ans = tmp
    else :
        for i in range(3) :
            person[i]+= Money[L]
            dfs(L+1)
            person[i]-= Money[L]


if __name__ == "__main__" :
    ans = sys.maxsize
    N = int(input()) # 지폐 금액 
    person = [0]*3 # 0,1,2 
    Money = []
    for _ in range(N) :
        Money.append(int(input()))
    dfs(0)
    print(ans)

• in4,5에서 time limit 이 발생함 -> 컴퓨터가 느려서 그래

약간 다른 내 풀이 코드 : 

def dfs(idx) :
    if idx == n :
        global ans 
        s = set(mp)
        if len(s) == 3 :
            ans = min(ans,max(s) - min(s)) 
        return 
    else :
        for i in range(3) :
            mp[i] += coin[idx]
            dfs(idx+1)
            mp[i] -= coin[idx]
        
if __name__=="__main__" :
    n = int(input())
    coin = []
    for i in range(n) :
        tmp = int(input())
        coin.append(tmp)
    ans = int(1e9)
    mp = [0,0,0]
    dfs(0)
    print(ans)

 

 

 

 

 

문제 6 - 알파코드 (DFS)

• 조금 복잡하다.

def dfs(L,P) :
    global cnt
    if L == n:
        cnt += 1
        for j in range(P) :
            print(chr(res[j]+64),end = '')
        print()
    else :
        for i in range(1,27) :
            if code[L] == i :
                res[P] = i 
                dfs(L+1, P+1) # 한자리 숫자 
            elif i >= 10 and code[L] == i // 10  and code[L+1] == i%10:
                res[P] = i
                dfs(L+2,P+1)


if __name__ == "__main__" :
    code = list(map(int,input()))
    n = len(code) # 지폐 금액 
    code.insert(n,-1) # 마지막에 -1 을 추가 # 2글자를 확인할 때  range를 벗어나는 오류를 피하기 위해서 
    res = [0]*(n+1)
    cnt = 0
    dfs(0,0)
    print(cnt)

문제 7 - 송아지 찾기 (BFS)

• 내가 만든 코드
• 몇몇 예제에는 맞는데 몇 예제에는 틀렸다.

  road = [-1,1,5]
  def bfs(s,d) :
    dq = deque()
    dq.append((s,d)) # 위치와 움직인 거리 
    while dq :
        tmp_s, tmp_d = dq.popleft()
        if tmp_s == E :
            print(tmp_d)
            break
        for i in road :
            if dis[tmp_s+i]==-1  :  
                dis[tmp_s+i] = tmp_d + 1
                dq.append((tmp_s+i,tmp_d + 1))
  

if name == "main" :
S, E = map(int,input().split())
dis = [-1]*10001 # 시작 위치가 0이라서 구분하기위해 -1로 설정
dis[S] = 0
bfs(S,0) # 위치 : s, 움직인 거리 : 0

<br>
- 강사님의 코드 


```py
MAX = 10000
ch = [0]*(MAX+1) #  check 
dis = [0] * (MAX+1) # 거리 저장 

n,m = map(int,input().split())
ch[n] = 1 # 확인하였음을 체크
dis[n] = 0  # 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 : # 좌표는 1부터 
            if ch[next] == 0 : # 방문을 하지 않았을 때만 
                dq.append(next)
                ch[next] = 1
                dis[next] = dis[now]+1
print(dis[m])

문제 8 - 사과나무(BFS)

dx = [0,-1,0,1]
dy = [1,0,-1,0]
n = int(input())
graph = [list(map(int,input().split())) for _ in range(n)] # 한줄씩 입력을 n번 
ch = [[0]*n for _ in range(n)] 
sum = 0 # 수확한 사과의 개수 
q = deque()
ch[n//2][n//2] = 1 
sum += graph[n//2][n//2]
q.append((n//2, n//2))
L=0 # level
while True :
    if L == (n//2) :
        break
    size = len(q)
    for i in range(size) :
        tmp = q.popleft()
        for j in range(4) :
            x = tmp[0]+ dx[j]
            y = tmp[1]+ dy[j]
            if ch[x][y]==0 :
                sum+=graph[x][y]
                ch[x][y] = 1
                q.append((x,y))
    L+=1 
print(sum)

문제 9 - 미로의 최단거리 통로(BFS)

• 내가 푼 풀이

from collections import deque

dx = [0,-1,0,1]
dy = [1,0,-1,0]
graph = [list(map(int,input().split())) for _ in range(7)]

dq = deque()
dis = [[-1] * 7 for i in range(7)]
dis[0][0] = 0
dq.append((0,0))
while dq:
    x,y = dq.popleft()
    if x == 6 and y == 6 :
        print(dis[6][6])
        sys.exit(0)
    for i in range(4) :
        nx,ny = x+dx[i],y+dy[i]
        if 0<=nx<=6 and 0<=ny<=6 :
            if dis[nx][ny] == -1 and graph[nx][ny] == 0 :
                dis[nx][ny] = dis[x][y]+1
                dq.append((nx,ny))

print(-1)

문제 10 - 미로탐색(DFS)

from collections import deque

dx = [0,-1,0,1]
dy = [1,0,-1,0]

def dfs(x,y) :
    global cnt
    if x == 6 and y == 6 :
        cnt+=1
    else :
        for i in range(4):
            nx = x+dx[i]
            ny = y + dy[i]
            if 0<=nx<=6 and 0<=ny<=6 and board[nx][ny] == 0 :
                board[nx][ny] = 1
                dfs(nx,ny)
                board[nx][ny] = 0


if __name__ == "__main__" :

    board = [list(map(int,input().split())) for _ in range(7)]
    cnt = 0
    board[0][0] = 1  #  방문한곳은 벽으로 만든다. 
    dfs(0,0)
    print(cnt)

문제 11 - 등산경로(DFS)

• 내가 만든 코드

  import sys
  dx = [0,-1,0,1]
  dy = [1,0,-1,0]
  

def dfs(x,y,val) : # x,y좌표, 해당 좌표의 높이
global cnt
if x == ex and y == ey :
cnt+=1
else :
for i in range(4):
nx = x+dx[i]
ny = y+dy[i]
if 0<=nx<n and 0<=ny<n and ch[nx][ny] == 0 :
if val < board[nx][ny] :
ch[nx][ny] = 1
dfs(nx,ny,board[nx][ny])
ch[nx][ny] = 0

if name == "main" :

n = int(input())
board = [list(map(int,input().split())) for _ in range(n)]
cnt = 0 # 등산경로의 개수 
ch = [[0]*n for _ in range(n)]
start = sys.maxsize
end = -sys.maxsize
sx ,sy = 0,0
ex,ey = 0,0
for i in range(n) :
    for j in range(n) :
        if start > board[i][j] :
            start = board[i][j]
            sx ,sy = i,j
        if end < board[i][j]:
            end = board[i][j]
            ex,ey = i,j
ch[sx][sy] = 1  # 시작지점 방문 표시  
dfs(sx,sy,start) # 시작지점 좌표, 시작지점의 높이
print(cnt)

 <br><br>
### 문제 12 - 단지번호 붙이기 

- bfs 풀이 

```py
from collections import deque

dx = [0,-1,0,1]
dy = [1,0,-1,0]

if __name__ == "__main__" :

    n = int(input())
    board = [list(map(int,input())) for _ in range(n)]
    cnt = []# 단지의 개수 
    sum = 0
    dq = deque()
    for i in range(n) :
        for j in range(n) :
            if board[i][j] == 1 :
                board[i][j] = 0
                dq.append((i,j))
                sum = 1 
                while dq :
                    x,y = dq.popleft()
                    for k in range(4):
                        nx = x+dx[k]
                        ny = y+dy[k]
                        if 0<=nx<n and 0<=ny<n and board[nx][ny] == 1 :
                            dq.append((nx,ny))
                            sum+=1 
                            board[nx][ny] =0
                cnt.append(sum)


    print(len(cnt))
    for i in sorted(cnt) :
        print(i)

문제 13 - 섬나라 아일랜드(BFS활용)

from collections import deque

dx = [0,-1,0,1,1,1,-1,-1]
dy = [1,0,-1,0,-1,1,1,-1]

if __name__ == "__main__" :

    n = int(input())
    board = [list(map(int,input().split())) for _ in range(n)]
    cnt = 0# 단지의 개수 
    dq = deque()
    for i in range(n) :
        for j in range(n) :
            if board[i][j] == 1 :
                board[i][j] = 0
                dq.append((i,j)) 
                while dq :
                    x,y = dq.popleft()
                    for k in range(8):
                        nx = x+dx[k]
                        ny = y+dy[k]
                        if 0<=nx<n and 0<=ny<n and board[nx][ny] == 1 :
                            dq.append((nx,ny))
                            board[nx][ny] =0
                cnt+=1


    print(cnt)

문제 14 - 안전영역(DFS)

import sys
sys.setrecursionlimit(10**6)# 재귀의 경우  # 이 시간이 지나면 알아서 멈춤 

dx = [0,-1,0,1]
dy = [1,0,-1,0]

def dfs(x,y,h) :
    ch[x][y] = 1 
    for i in range(4) :
        nx = x+dx[i]
        ny = y +dy[i]
        if 0<=nx<n and 0<=ny<n and ch[nx][ny] == 0 and board[nx][ny] > h: 
            dfs(nx,ny,h)




if __name__ == "__main__" :
    n = int(input())
    cnt = 0 # 안정영역의 개수 
    res = 0 # 최종 답 
    board = [list(map(int,input().split())) for _ in range(n)] 
    for h in range(100) : # 높이 
        ch =[[0]*n for _ in range(n)]
        cnt = 0
        for i in range(n) :
            for j in range(n) :
                if ch[i][j] == 0 and board[i][j] > h :
                    cnt+=1
                    dfs(i,j,h)
        res = max(cnt,res)
        if cnt == 0 :
            break
    print(res)

• 컴퓨터가 느려서 그런지 4,5 번이 time limit에러가 발생한다.
• 파이썬 재귀의 경우 input의 크기가 클 때 sys.setrecursionlimit(10** 6)를 이용한다.

문제 15 - 토마토(BFS)

• 내가 만든 코드

  import sys
  from collections import deque
  from sys import stdin
  input = stdin.readline
  

dx = [0,-1,0,1]
dy = [1,0,-1,0]

def bfs() :
while dq :
x,y = dq.popleft()
for i in range(4) :
nx ,ny= x + dx[i],y + dy[i]
if 0<=nx<n and 0<=ny < m and board[nx][ny]==0 :
board[nx][ny] = board[x][y] +1
dq.append((nx,ny))

if name == "main" :
m,n = map(int,input().split())
board = [list(map(int,input().split())) for _ in range(n)]
dq =deque()
for i in range(n) :
for j in range(m) :
if board[i][j] == 1 :
dq.append((i,j))
bfs()
max_day = 0
for j in board :
for i in j :
if i == 0 :
print(-1)
sys.exit(0)
if max_day <i :
max_day = i
print(max_day-1) # 1부터 시작해서 +=1 1을 하므로

 <br><br>
### 문제 16 - 사다리 타기(DFS)

```py
dx = [0,-1,0,1]
dy = [1,0,-1,0]

def dfs(x,y) :
    ch[x][y] =1 
    if x == 0 :
        print(y)
    else :
        if y-1 >= 0 and board[x][y-1]==1 and ch[x][y-1] == 0 : # 왼쪽으로 이동 
            dfs(x,y-1)
        elif y+1<10 and board[x][y+1] == 1 and ch[x][y+1] == 0 : # 오른쪽
            dfs(x,y+1)
        else : # 위쪽으로 
            dfs(x-1,y) 

if __name__ == "__main__" :
    board = [list(map(int,input().split())) for _ in range(10)] 
    ch = [[0]*10 for _ in range(10) ]
    for y in range(10) :
        if board[9][y] == 2 : # 도착지
            dfs(9,y) 

• 아래부터 시작해서 왼쪽, 오른쪽을 살피고 그 후에 아무것도 없으면 위쪽으로 간다.문제 17 - 피자배달거리 (DFS)
• 
  
  

import sys 
def dfs(L,s) :
    global res
    if  L ==m :
        sum = 0
        for j in range(len(hs)) : 
            x1 = hs[j][0]
            y1 = hs[j][1] 
            dis = sys.maxsize
            for x in cb : # 선택된 피자집의 좌표
                x2 = pz[x][0]
                y2 = pz[x][1]
                dis = min(dis, abs(x1-x2) + abs(y1-y2))
            sum += dis 
        if sum < res :
            res = sum
    else :
        for i in range(s,len(pz)) :
            cb[L] = i 
            dfs(L+1, i+1)

if __name__ == "__main__" :
    n,m = map(int,input().split())
    board = [list(map(int,input().split())) for _ in range(n)] 
    hs = []
    pz = [] 
    cb = [0]*m # 선택된 피자집 
    res = sys.maxsize
    for i in range(n) :
        for j in range(n) :
            if board[i][j] == 1 :
                hs.append((i,j))
            elif board[i][j] == 2:
                pz.append((i,j))
    dfs(0,0)
    print(res)