[DFS/BFS+DP]2206번, 11722번

1. 벽 부수고 이동하기

링크 - https://www.acmicpc.net/problem/2206

코드

from collections import deque
import sys

input = sys.stdin.readline

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

n,m = map(int,input().split())

graph=[]

#그래프 입력받기
for i in range(n):
    graph.append([])
    arr = input().rstrip()
    for j in range(m):
        graph[i].append(int(arr[j]))
        
        
def bfs(sx,sy):
    q = deque()
    visited=[[[False]*2 for i in range(m)] for j in range(n)]
    #x,y,flag,count
    q.append([sx,sy,0,1])
    visited[sx][sy][0]=True
    
    while q:
        x,y,w,count = q.popleft()
        if x==n-1 and y==m-1:
            return count
        
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0<=nx<n and 0<=ny<m:
                if visited[nx][ny][w]==False:
                    if graph[nx][ny]==0:
                        q.append([nx,ny,w,count+1])
                        visited[nx][ny][w]=True
                    else:
                        if w==0:
                            q.append([nx,ny,1,count+1])
                            visited[nx][ny][1]=True
    
    return -1

print(bfs(0,0))

일단 코드는 더럽다-!
처음에는 visted배열을 2차원으로 했었는데 11%에서 틀렸다.

https://www.acmicpc.net/board/view/69214
이 링크에 있는 반례를 이용해서 풀었더니 27이 아니라 -1이 나왔었다.

벽을 부수고 갈 때는 visited 배열을 다르게 생각해야 한다는 걸 알게 돼서 배열을 3차원으로 변경했다.

2. 가장 긴 감소하는 부분 수열

링크 - https://www.acmicpc.net/problem/11722

코드

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int,input().split()))
arr.reverse()
dp = [1]*n

for i in range(1,n):
    for j in range(0,i):
        if arr[i]>arr[j]:
            dp[i]=max(dp[i],dp[j]+1)

print(max(dp))

dp의 초심을 찾고자... 여행을 떠나렵니다..
구라고요 쉬운거부터 다시 풀어볼라고요..
https://stonejjun.tistory.com/24
여기 있는 문제 천천히.. 다 풀어보는게 내 자그마한 목표..