[DP+DFS/BFS] 6359번, 3187번

1. 만취한 상범

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

코드

t = int(input())

for _ in range(t):
    n = int(input())
    #처음에 모든 문을 열기 때문에 1로 설정
    dp = [1]*(n+1)
    for i in range(2,n+1):
        for j in range(i,n+1,i):
            dp[j]= -dp[j]
    
    print(dp.count(1)-1)

시간초과날까봐 걱정했는데 n이 100까지만 주어져서 정답처리가 됐었다.

2. 양치기 꿍

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

코드

from collections import deque
import sys

input = sys.stdin.readline

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

r,c = map(int,input().split())

visited = [[False]*(c) for i in range(r)]
#그래프 입력받기
graph=[]
for i in range(r):
    line = input().rstrip()
    graph.append([])
    for j in line:
        graph[i].append(j)
def bfs(sx,sy):
    q= deque()
    #위치 늑대, 양
    q.append([sx,sy])
    visited[sx][sy]=True
    w=0
    s=0
    while q:
        x,y= q.popleft()
        if graph[x][y]=='v':
            w+=1
        elif graph[x][y]=='k':
            s+=1
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0<=nx<r and 0<=ny<c:
                if graph[nx][ny]!='#' and visited[nx][ny]==False:
                    visited[nx][ny]=True
                    q.append([nx,ny])
                    
    return w,s

ww=0
ss=0
for i in range(r):
    for j in range(c):
        if visited[i][j]==False and graph[i][j]!='#':
            w,s = bfs(i,j)
            if w>=s:
                ww+=w
            else:
                ss+=s

print(ss,ww)

문제에서 대각선 이동은 없다고 했으므로 상하좌우 탐색만 해주었다.
울타리마다 탐색하는 문제였다.
계속 값이 다르게 나왔었는데 시작부분에서 해당위치에 양 혹은 늑대가 있는지를 체크를 안해줘서 그랬었다.
그래서 검사하는 부분을 pop을 하고 검사하도록 위치를 바꿨었다.