2178번, 10026번, 11727번

1. 미로탐색

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

코드

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())

visited=[[False]*(m+1) for i in range(n+1)]
#(n+1)*(m+1) 그래프 생성
graph = [[0]*(m+1) for i in range(n+1)]

#그래프 값 넣어주기
for i in range(1,n+1):
    line = input()
    for j in range(m):
        graph[i][j+1]=int(line[j])


def bfs(count):
    q=deque()
    q.append((1,1,count))
    visited[1][1]=True
    
    while q:
        x,y,count = q.popleft()
        for i in range(len(dx)):
            nx=x+dx[i]
            ny=y+dy[i]
            #범위 내 인지 확인
            if nx==n and ny==m:
                return count+1
            if 1<=nx<=n and 1<=ny<=m:
                if visited[nx][ny]==False and graph[nx][ny]==1:
                    q.append((nx,ny,count+1))
                    visited[nx][ny]=True

print(bfs(1))

기본적인 4방향 dfs,bfs문제였다.

2. 적록색약

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

코드

from collections import deque
import sys

input = sys.stdin.readline
dx=[-1,1,0,0]
dy=[0,0,-1,1]

n= int(input())
graph = [[0]*(n+1) for i in range(n+1)]
visited=[[False]*(n+1) for i in range(n+1)]

#그래프 값 넣어주기
for i in range(1,n+1):
    line = input()
    for j in range(n):
        graph[i][j+1]=line[j]

#색약 아닌 사람
def bfs(sx,sy):
    q= deque()
    q.append([sx,sy])
    visited[sx][sy]=True
    
    while q:
        x,y = q.popleft()
        for i in range(len(dx)):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0<nx<=n and 0<ny<=n:
                if graph[nx][ny]==graph[x][y] and visited[nx][ny]==False:
                    visited[nx][ny]=True
                    q.append([nx,ny])
    return 



count=0
for i in range(1,n+1):
    for j in range(1,n+1):
        if visited[i][j]==False:
            count+=1
            bfs(i,j)
print(count,end=" ")

#G를 R로 바꾸기
for i in range(1,n+1):
    for j in range(1,n+1):
        if graph[i][j]=='G':
            graph[i][j]='R'

visited=[[False]*(n+1) for i in range(n+1)]
count=0
for i in range(1,n+1):
    for j in range(1,n+1):
        if visited[i][j]==False:
            count+=1
            bfs(i,j)           
print(count)

벽부수기인가 그거 풀려다가 오래 걸릴 거 같아서 걍 줄행랑 치고 푼 문제... ㅎ
위의 문제랑 거의 똑같은데 bfs를 2번 돌리는 문제였다.
적록색약인 사람들이 보는 개수를 체크해주기 위해서 'G'를 모두 'R'로 바꿔서 같은 함수를 이용했다.

3. 2*n 타일링

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

코드

import sys
input = sys.stdin.readline
n = int(input())

dp=[0]*(1001)
dp[1]=1
dp[2]=2

for i in range(3,1001):
    dp[i] =(dp[i-1]+dp[i-2])
    
print(dp[n]%10007)

전에 책에서 푼 문제랑 같은 dp 문제였다. 다른 점은 책에 있는 문제는 타일 3개였는데 이 문제는 타일 2개를 이용하는 거였다.

타일 3개 이용하는건 11727번 문제였는데 내가 11727번 문제에 계속 이 코드를 넣고 돌려서 계속 틀렸다고 결과가 나왔었다ㄱ-