[백준] 4796, 2178, 2606 (파이썬)

오늘도 어제와 같이 그리디 문제와 BFS,DFS 문제를 풀었다. 하면서 느낀 점은 BFS,DFS에 관한 부분이 아직 익숙하지 않다는 것, 알고리즘에 관한 경험이 많이 필요하다고 느낀 하루였다. BFS, DFS문제는 적응이 될 때까지 풀이할 예정이다. 또한 코드가 길어질수록 헷갈리는 경우가 많으니 알고리즘을 손으로 쓰면서 코드를 작성해야겠다.

백준 4796번 캠핑

import sys
count = 1
while True:
    L,P,V = map(int,sys.stdin.readline().split())
    if L==0 and P==0 and V==0:
        break
    res = L*(V//P)
    if V%P<L:
        res+=V%P
    else:
        res+=L
    print('Case %d: %d' %(count,res))
    count += 1

백준 2178번 미로 탐색

import sys
from collections import deque
N,M = map(int,sys.stdin.readline().split())
graph = []
for i in range(N):
    graph.append(list(map(int,sys.stdin.readline().strip())))
dx = [-1,1,0,0]
dy = [0,0,-1,1]
def bfs(x,y):
    queue = deque()
    queue.append([x,y])
    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 범위를 벗어난 경우 무시
            if nx<0 or ny<0 or nx>=N or ny>=M:
                continue
            # 0일 경우 무시
            if graph[nx][ny]==0:
                continue
            # 최단 거리 기록
            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y]+1
                queue.append([nx,ny])
    return graph[N-1][M-1]
print(bfs(0,0))

백준 2606번 바이러스

# 아직까지는 적응을 하지 못한 느낌, 노력이 필요하다.
import sys
com = int(sys.stdin.readline())
ssang = int(sys.stdin.readline())
graph = [[]*com for _ in range(com+1)]
for _ in range(ssang):
    a,b = map(int,sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)
cnt = 0
visited = [False]*(com+1)
def dfs(x):
    global cnt
    visited[x] = True
    for i in graph[x]:
        if not visited[i]:
            dfs(i)
            cnt+=1
dfs(1)
print(cnt)