BFS, DP

SWEA 1226. [S/W 문제해결 기본] 7일차 - 미로1

문제 링크

from collections import deque
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 nx > 15 or ny<0 or ny>15:
                continue
            if graph[nx][ny] == 1:
                continue

            if graph[nx][ny] != 1:
                graph[nx][ny] = 1
                queue.append((nx, ny))

for _ in range(10):
    i = int(input())
    graph = [list(map(int,list(input()))) for _ in range(16)]
    # visited = [False for _ in range(16 for _ in range(16))]
    for row in range(16):
        for col in range(16):
            if graph[row][col] == 2:
                start_row, start_col = row, col
            if graph[row][col] == 3:
                end_row, end_col = row, col

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

    bfs(start_row, start_col) #start node
    if graph[end_row][end_col] == 1:
        print('#{} {}'.format(i, 1))
    else:
        print('#{} {}'.format(i, 0))

BFS 기본 문제였다.

1. nx,ny로 각 단계에서 4방향으로 순회하는 것
2. 큐를 사용해서 BFS 구현

백준 14501 퇴사

참고코드

n = int(input()) # 일수
t = [] # 일하는 데 걸리는 시간
p = [] # 일한 후 수익
result = 0
for _ in range(n):
    a, b = map(int, input().split())
    t.append(a)
    p.append(b)

d = [0]*(n+1) # 정해진 기간만큼 일한 다음날 수익을 얻는다.
for i in range(n+1):
    for j in range(0, i):
        d[i] = max(d[i], d[j]) # 수익을 얻도록 일하기 시작한 날에서 아무것도 안했을 때의 수익
        if t[j]+j == i:
            d[i] = max(d[i], d[j]+p[j]) # j날부터 일하고 나서 i날에 수익을 얻을때 
    result = max(result, d[i])
print(result)

1. dp문제였다. 그러나 dp는 아직도 감이 안잡힌다.
2. d를 설정해서 수익을 얻는 날 측면에서 생각해야했다.