2022.01.14

백준 1697 숨바꼭질

# 1697 숨바꼭질
from collections import deque

N, K = map(int,input().split())

# 리스트 인덱스에 점으로 이동하는 시간을 저장하기 위해서 arr생성
# x-1이 더 빠른 경우도 있기 때문에 가장 큰 값에서 +2해준다.
if N >= K:
    arr = [0] * (N+2)
else:
    arr = [0] * (K+2)
    
def bfs(x):
    queue = deque()
    queue.append(x)
    arr[x] = 0
    if x == K:   # N == K 같은 경우 0 리턴
        return 0
    while queue:
        a = queue.popleft()
        dx = [1,-1,a]
        for i in range(3):
            nx = a + dx[i]
            if 0 <= nx < len(arr) and arr[nx] == 0:
                queue.append(nx)
                arr[nx] = arr[a] + 1
bfs(N)
print(arr[K])

x와 K 값이 같을 때 값을 지정해주는 것과 arr의 범위를 잘 못 정해줘서

문제가 무엇일까 하고 한참을 쳐다보았었다.

# 1436 영화감독 숌
N = int(input())
arr = []

d = 665
while len(arr) != N:
    a = list(str(d))
    for i in range(len(a)-2):
        if a[i]+a[i+1]+a[i+2] == '666':
            arr.append(d)
            break
    d += 1
print(arr[N-1])

#1158
from collections import deque

N, K = map(int, input().split())

R = []
queue = deque()
for i in range(1,N+1):
    queue.append(i)
    
while queue:
    for i in range(K-1):
        queue.append(queue.popleft())
    R.append(queue.popleft())
    
print('<', end = '')
print(*R, sep = ', ', end = '')
print('>')

백준 7569 토마토

from collections import deque

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

graph = []

for _ in range(h):
    graph.append([ list(map(int,input().split())) for _ in range(n) ])

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

queue = deque()

def bfs():
    for i in range(h):
        for j in range(n):
            for k in range(m):
                if graph[i][j][k] == 1:
                    queue.append((i,j,k))
    
    while queue:
        x,y,z = queue.popleft()
        for i in range(6):
            nx = x + dx[i]
            ny = y + dy[i]
            nz = z + dz[i]

            if 0 <= nx < h and 0 <= ny < n and 0 <= nz < m :
                if graph[nx][ny][nz] == 0 :
                    queue.append((nx,ny,nz))
                    graph[nx][ny][nz] = graph[x][y][z] + 1

bfs()
R = []
for i in range(h):
    for j in range(n):
        if 0 in graph[i][j]:
            R.append(0)
        else:
            R.append(max(graph[i][j]))
if 0 in R:
    print(-1)
else:
    print(max(R)-1)

처음에 2차원 배열로 풀려다가 상자 층이 넘어가는 것을

인접면으로 탐색하는 걸 해결 못해서 포기했다.

결국 3차원으로 풀었는데 어제 풀었던 7576번 문제와 똑같고

차원이 하나 추가돼서 좌표설정만 헷갈리지 않으면 됐다.

#1181
N = int(input())
arr = [input() for i in range(N)]

H = list(set(arr)) # 중복 제거
H.sort()
H.sort(key = len)  # 길이값으로 또 정렬
for i in H:
    print(i)

#1085
x, y, w, h = map(int, input().split())
print(min(x,y,w-x,h-y))

2022.01.11

백준 7576 토마토

#7576
from collections import deque

M, N = map(int, input().split())
arr = []
for i in range(N):
    arr.append(list(map(int,input().split())))
    
def BFS(graph):
    queue = deque()
    for i in range(N):
        for j in range(M):
            if arr[i][j] == 1:
                queue.append((i,j)) #토마토가 여러개 있을 때를 해결
    
    dx = [0,0,-1,1]
    dy = [-1,1,0,0]
    while queue:
        a, b = queue.popleft()
        for i in range(4):
            nx = a + dx[i]
            ny = b + dy[i]
            if 0 <= nx < N and 0 <= ny < M:
                if arr[nx][ny] == 0:
                    queue.append((nx,ny))
                    arr[nx][ny] = arr[a][b] + 1
            
BFS(arr)
R = []
for i in range(N):
    if 0 in arr[i]:
        R.append(0)
    else:
        R.append(max(arr[i]))
if 0 in R:
    print(-1)
else:
    print(max(R)-1)       

토마토가 여러 개 존재하면 어떻게 풀지?라는 의문을 반복문을 통해 해결했더니 

다른 BFS 문제와 별다를 게 없었다. 또 다른 점이라면 출력 조건이 좀 많다는 점?

체스판 다시 칠하기

# 1018
W = [['W','B','W','B','W','B','W','B'],
     ['B','W','B','W','B','W','B','W'],
     ['W','B','W','B','W','B','W','B'],
     ['B','W','B','W','B','W','B','W'],
     ['W','B','W','B','W','B','W','B'],
     ['B','W','B','W','B','W','B','W'],
     ['W','B','W','B','W','B','W','B'],
     ['B','W','B','W','B','W','B','W']]
B = [['B','W','B','W','B','W','B','W'],
     ['W','B','W','B','W','B','W','B'],
     ['B','W','B','W','B','W','B','W'],
     ['W','B','W','B','W','B','W','B'],
     ['B','W','B','W','B','W','B','W'],
     ['W','B','W','B','W','B','W','B'],
     ['B','W','B','W','B','W','B','W'],
     ['W','B','W','B','W','B','W','B'],]

N, M = map(int,input().split())
arr = []
for i in range(N):
    arr.append(list(input()))
    
def chess(x,y):
    wcnt = 0
    bcnt = 0
    if x + 8 <= N and y + 8 <= M:
        for i in range(8):
            for j in range(8):
                if arr[i+x][j+y] == W[i][j]:
                    wcnt += 1
                else:
                    bcnt += 1
    return R.append(max(wcnt,bcnt))
                      
R = []
for i in range(N):
    for j in range(M):
        chess(i,j)
print(64-max(R))

첫 칸이 흰색이거나 검은색인 두 가지 경우의 수만 있다고 해서 먼저 두 가지 케이스를 리스트로 

만들어놨다. 그리고 이 케이스를 입력받는 N*M에 한 칸씩 넘어가면서 대조해보고 수정할 값이 

가장 적은 것을 가져왔다.

리스트를 만들어서 대조하기 전에 ['W', 'B'] 나 ['B', 'W']같이 짧은 리스트로도 풀 수 있을 거 같은 

느낌이지만 어떻게 풀어야할지 생각이 안 나네 다음에 시도해봐야겠다.

A+B - 4

#10951
while True:
    try:
        A , B = map(int, input().split())
        print(A+B)
    except:
        break

따로 몇 번을 반복해야 하는지 주어지지 않는다. 때문에 while문으로 무한루프를 만들고

try, except 구문을 사용하여 오류가 발생했을 때 (입력값이 주어지지 않을 시)

while문의 무한루프에서 빠져나오게 만들었다.

X보다 작은 수

# 10871
N, X = map(int, input().split())
A = list(map(int, input().split()))
for i in A:
    if i < X:
        print(i, end = ' ')