Coding 공부

N = int(input())
 
if N >= 90:
    print('A')
elif N >= 80:
    print('B')
elif N >= 70:
    print('C')
elif N >= 60:
    print('D')
else:
    print('F')

# 7576번 문제 
# 1은 익은 토마토 0은 익지않은 토마토
 
N,M = map(int,input().split())
 
tomatoarray = [list(map(int,input().split())) for _ in range(M)]
 
dx = [-1,1,0,0]
dy = [0,0,1,-1]
tomatocnt = 0
total = N*M
tomato = []
for x in range(M):
    for y in range(N):
        if tomatoarray[x][y] == 1:
            tomato.append((x,y))
            tomatocnt += 1
        elif tomatoarray[x][y] == -1:
            total -= 1
result = -1
day = 0
if total == tomatocnt:
    result = 0
else:
    while tomato:
        new_tomato = []
        for x,y in tomato:
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0<=nx<M and 0<=ny<N:
                    if not tomatoarray[nx][ny]:
                        tomatoarray[nx][ny] = 1
                        new_tomato.append((nx,ny))
                        tomatocnt += 1
 
 
        day += 1
        if tomatocnt == total:
            result = day
            break
        if len(new_tomato):
            tomato = [row[:] for row in new_tomato]
        else:
            result = -1
            break
 
 
 
print(result)

익은 토마토를 기준으로 상하좌우로 인접한 토마토들만 익는다. 

1일차의 토마토가 익힌 인접 토마토들이 2일차에 새로운 토마토들을 익히게 된다.

그러므로 1일차의 토마토들은 필요 없어진다.

이런한 점을 이용해, 반복문을 통해 새롭게 익은 토마토들을 찾아내고, 그때 토마토 개수를 늘려준다. 

그리고 난뒤 전체 행렬의 크기와 토마토 개수가 같으면 반복문을 탈출하고,

새롭게 익은 토마토들이 있으면, 더 익힐 가능성이 있으므로, 그 리스트를 복사해서 반복해준다.

하지만 새롭게 익은 토마토들이 없으면, 더이상 익힐 가능성이 없으므로, 반복문을 탈출해서 -1을 출력해주면 된다.

# 7569 토마토
 
M,N,H = map(int,input().split())
 
dx = [-1,1,0,0,0,0]
dy = [0,0,-1,1,0,0]
dz = [0,0,0,0,-1,1]
 
tomatoarray =[ [list(map(int,input().split())) for _ in range(N)] for _ in range(H)]
# tomato dz dx dy
# H,N,M
 
total = N*M*H
tomatocnt = 0
tomatos = []
result = -1
day = 0
for x in range(N):
    for y in range(M):
        for z in range(H):
            if tomatoarray[z][x][y] == 1:
                tomatos.append((x,y,z))
                tomatocnt += 1
            elif tomatoarray[z][x][y] == -1:
                total -= 1
if total == tomatocnt:
    result = 0
else:
    while tomatos:
        new_tomato = []
        for x,y,z in tomatos:
            for i in range(6):
                nx = x + dx[i]
                ny = y + dy[i]
                nz = z + dz[i]
                if 0<=nx<N and 0<=ny<M and 0<=nz<H:
                    if not tomatoarray[nz][nx][ny]:
                        tomatoarray[nz][nx][ny] = 1
                        tomatocnt += 1
                        new_tomato.append((nx,ny,nz))
        day += 1
        if tomatocnt == total:
            result = day
            break
        if len(new_tomato):
            tomatos = [row[:] for row in new_tomato]
        else:
            result = -1
            break
print(result)

이 문제는 7576번 문제의 3D 버전이다 여기서 조심해야할 것은 3차원이고, x,y,z의 순서를 조심해주면 된다.

보통 문제를 풀때 나같은 경우 x축을 행으로 하고 y축을 열로 한다. 자신만의 기준을 가지고, 헷갈리지 않게 조심하면 될 것 같다.

기본 원리는 7576번하고 같다.

import sys
 
N = int(sys.stdin.readline())
array = [0]* 2000001
for _ in range(N):
    num = int(sys.stdin.readline())
    num += 1000000
    array[num] += 1
 
for num in range(2000001):
    print(f'{num-1000000}\n'*array[num],end='')

문제에서 수의 크기가 100만이므로 200만1개의 리스트를 만들어주고 반복문을 돌려주었다.

def dfs(N):
    stack = [1]
    visted = [0]*(N+1)
    cnt = 0
    visted[1] = 1
    while stack:
        num = stack.pop()
        cnt += 1
        for ind in graph[num]:
            if not visted[ind]:
                visted[ind] = 1
                stack.append(ind)
    return cnt - 1
 
N = int(input())
M = int(input())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
 
 
print(dfs(N))

기본적인 DFS였다. 방향성이 없기 때문에, graph라는 리스트에 양방향으로 전부 저장시켜주고, 방문을 표시해준뒤, 1번 컴퓨터에 연결된 모든 노드들을 찾아주면 된다.

# 2178번
# 문제
# N*M 크기의 배열
# (1,1) => (N,M) 까지 가야한다.
from collections import deque
dx = [-1,1,0,0]
dy = [0,0,1,-1]
N,M = map(int,input().split())
 
maze = [list(input()) for _ in range(N)]
 
 
visted = [[0]*M for _ in range(N)]
 
 
stack = deque()
stack.append((0,0))
visted[0][0] = 1
flag = False
while not flag:
    x,y = stack.popleft()
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx == N-1 and ny == M-1:
            flag = True
            visted[nx][ny] = visted[x][y] + 1
            break
        elif 0<=nx<N and 0<=ny<M:
            if not visted[nx][ny] and maze[nx][ny] == '1':
                visted[nx][ny] = visted[x][y] + 1
                stack.append((nx,ny))
print(visted[N-1][M-1])

이 문제는 시작위치와 도착위치가 정해져있고, 최소 이동거리를 찾는것이므로, visited라는 maze와 똑같은 사이즈의 리스트를 만들어두고, 그 안에 이동거리를 저장해주었다. 그리고 도착위치에 도착하면 break를 해주었고, 그때의 flag를 바꿔주어서 상단의 while문도 빠져나갈수 있게 해주었다.

N,M = map(int,input().split())
 
hear = {}
for _ in range(N):
    hear[input()] = 1
 
result = []
for _ in range(M):
    see = input()
    if hear.get(see):
        result.append(see)
 
result.sort()
 
print(len(result))
 
print('\n'.join(result))

이 부분은 dictionary에서 쉽게 쓸수 있는 get 메소드를 통해 존재하는 경우 result 리스트에 저장해두고 출력해주었다.

# 1697 숨바꼭질
 
#  수빈이는 N 동생은 K 
#  수빈이는 X-1 or X+1 2*X
 
 
N,M = map(int,input().split())
 
result = 0
stack = [(N,0)]
visited = [0]*100001
while stack:
    cu_n,cnt = stack.pop(0)
    if cu_n == M:
        break
    if 0<= cu_n <= 100000:
        if 0<= cu_n -1 <= 100000:
            if not visited[cu_n-1]:
                visited[cu_n-1] =1
                stack.append((cu_n-1,cnt+1))
        if 0<= cu_n+1 <= 100000:
            if not visited[cu_n+1]:
                visited[cu_n+1] =1
                stack.append((cu_n+1,cnt+1))
        if 0<= cu_n*2 <= 100000:
            if not visited[cu_n*2]:
                visited[cu_n*2] =1
                stack.append((cu_n*2,cnt+1))
print(cnt)

BFS의 일종으로 볼 수 있다.

 현재 위치에서 +1, -1 , *2 를 했을 때의 값을 추가해주고, BFS에서는 먼저 들리는 곳이 가장 가까운 곳이므로, 한번 방문했던 곳은 연산량을 줄이기 위해 방문을 표시해주었다. 그리고 최초로 목표 위치인 M을 방문하면 반복문을 멈추게 했다.