arr이란 리스트에 2차원배열로 회의 시작시간과 끝나는시간을 저장해 준 다음 회의가 끝나는 시간을 오름차순으로 정렬하였고, 만약 끝나는 시간이 같다면 시작시간을 오름차순으로 정렬하였다.
arr = []
now,cnt = 0,0 # now (현재 시간) , cnt (회의
N = int(input())
for i in range(N):
st,ed = map(int,input().split())
arr.append([st,ed]) # 2차원 배열에 시작,끝나는 시간 저장
arr = sorted(arr, key=lambda x: (x[1], x[0])) # 인덱스1을 기준으로 오름차순 정렬
# 만약 인덱스1 의 값이 같다면 인덱스 0값을 기준으로 오름차순 정렬
for i in range(N):
if now <= arr[i][0]: # 현재시간이 시작시간과 같거나 적으면
now = arr[i][1] # 현재시간을 회의가 끝나는 시간으로 변경
cnt += 1
print(cnt)
import sys
input = sys.stdin.readline # 시간초과를 방지하기 위한 코드
N = int(input())
stack = []
for i in range(N):
tmp = int(input())
if tmp == 0: # 0이 입력된다면 stack의 마지막부분을 제거
stack.pop()
else:
stack.append(tmp)
print(sum(stack)) # for문이 끝나면 남아있는 stack의 합을 구함
TC = int(input())
for tc in range(1,TC+1):
N = int(input())
cnt = 0
def dfs(level):
global cnt
if level > N: # level의 값이 목표값을 넘어가면 리턴
return
if level == N: # 목표값이 되었을 때, cnt + 1
cnt += 1
return
for i in range(1,4): # 1~3 까지의 수의 중복순열 구하기
dfs(level+i)
dfs(0)
print(cnt)
N,M = map(int,input().split())
path = [''] * M
used = [0] * N
def dfs(level):
if level == M:
for i in range(M):
print(path[i], end = ' ')
print()
return
for j in range(N):
if used[j] == 0: # 사용하지 않은 수라면
used[j] = 1
path[level] = j+1 # path에 값 저장
dfs(level+1)
used[j] = 0
dfs(0)
import copy
from collections import deque
N = int(input())
arr = [list(map(int,input().split())) for _ in range(N)]
acc = copy.deepcopy(arr)
directy = [-1,1,0,0]
directx = [0,0,-1,1]
result = []
def bfs(y,x): # 인접해있는 지역을 모두 False로 바꿈
q = deque([(y,x)])
arr[y][x] = False
while q:
y,x = q.popleft()
for k in range(4):
dy = directy[k] + y
dx = directx[k] + x
if dy >= N or dy < 0 or dx >= N or dx < 0: # 배열을 벗어난다면 continue
continue
if arr[dy][dx] != False: # 목표좌표가 False이 아니라면 False로 바꿔줌
arr[dy][dx] = False
q.append([dy,dx])
for l in range(101): # 높이가 최대 100이므로 100까지 증가하는 for 문
arr = copy.deepcopy(acc) # for문을 돌 때마다 arr배열과 cnt(안전영역) 초기화
cnt = 0
for j in range(N):
for i in range(N):
if arr[j][i] <= l: # 비의 양보다 낮으면 해당 좌표를 False로 만들어줌
arr[j][i] = False
for j in range(N):
for i in range(N):
if arr[j][i] != False: # False이 아니라면 bfs 함수 호출하고 cnt += 1
bfs(j,i)
cnt += 1
result.append(cnt) # 안전영역을 result에 추가
if cnt == 0: # 모든지역이 물에 잠긴다면 그 이후는 의미 없으므로 break
break
print(max(result))
from collections import deque
TC = int(input())
for tc in range(TC):
N = int(input())
used = [[0]*N for _ in range(N)] # 방문체크를 위한 used 배열
arr = [[-1]*N for _ in range(N)]
y,x = map(int,input().split())
used[y][x] = 1
arr[y][x] = 0 # 시작위치는 0부터 시작
q = deque([(y,x)])
j,i = map(int,input().split())
arr[j][i] = 'ed'
directy = [-1,-2,-2,-1,1,2,2,1]
directx = [-2,-1,1,2,-2,-1,1,2]
result = 0
def bfs():
global result,q
while q:
y,x = q.popleft()
for k in range(8):
dy = directy[k] + y
dx = directx[k] + x
if dy >= N or dy < 0 or dx >= N or dx < 0: # 배열을 벗어나면 continue
continue
if arr[dy][dx] == 'ed': # 도착점에 도착하면 result에 값 저장하고 종료
result = arr[y][x] + 1
q=[]
break
if used[dy][dx] == 0: # 방문하지 않은곳만 방문
used[dy][dx] = 1
arr[dy][dx] = arr[y][x] + 1
q.append([dy,dx])
if j == y and i == x: # 시작점과 도착점이 같다면 0출력
print("0")
else:
bfs()
print(result)
물이 차있는 지역이 없을 수 도있고 여러개인 경우를 고려하지 못해서 처음엔 런타임에러가 떴다.
도착점을 제외하고는 고슴도치는 물이 찰 예정인 칸으로 갈 수 없으므로 목표좌표에 고슴도치부터 이동시키고 물과 고슴도치가 만난다면 물로 표시했다
from collections import deque
N,M = map(int,input().split())
arr = [list(input()) for _ in range(N)]
used = [[0] * M for _ in range(N)] # 물의 방문체크
used2 = [[0] * M for _ in range(N)] # 고슴도치의 방문체크
directy = [-1,1,0,0]
directx = [0,0,-1,1]
q = deque()
tmp1,tmp2 = [],[]
result,flag = 0,0
for j in range(N):
for i in range(M):
if arr[j][i] == 'S':
tmp1 = [j,i,'S'] # 고슴도치의 위치
arr[j][i] = 0
used2[j][i] = 1
if arr[j][i] == '*': # 물이 있는 좌표를 tmp2에 저장
tmp2.append([j,i,'*'])
used[j][i] = 1
flag += 1
if arr[j][i] == 'D':
used[j][i] = 1 # 도착점에는 물이 도착할 수 없도록 used에 방문체크
q.append(tmp1) # 고슴도치부터 q에 추가
for i in range(flag):
q.append(tmp2[i])
def bfs():
global result,q
while q:
y,x,s = q.popleft()
# for i in range(N):
# print(*arr[i])
# print(result, q)
for k in range(4):
dy = directy[k] + y
dx = directx[k] + x
if dy >= N or dy < 0 or dx >= M or dx < 0 or arr[dy][dx] == 'X': # 배열을 벗어나거나 벽이라면 continue
continue
if s == 'S': # 고슴도치
if arr[dy][dx] == 'D' and used[y][x] == 0: # 목적지에 도착했다면 result에 이동거리 저장
result = arr[y][x] + 1
q = []
break
if used2[dy][dx] == 0 and used[dy][dx] == 0 and used[y][x] == 0: # 고슴도치가 방문하지 않았고, 목표지점과 현재위치가 물이 없다면 이동
used2[dy][dx] = 1
arr[dy][dx] = arr[y][x] + 1
q.append([dy,dx,'S'])
if s == '*': # 물
if used[dy][dx] == 0: # 방문안한곳 방문
used[dy][dx] = 1
arr[dy][dx] = '*'
q.append([dy,dx,'*'])
bfs()
if result == 0: # 도착하지못하면 KAKTUS 출력
print("KAKTUS")
else:
print(result)
from collections import deque
M,N,H = map(int,input().split())
tomato = []
q = deque()
directy = [-1,1,0,0,0,0]
directx = [0,0,1,-1,0,0]
directk = [0,0,0,0,-1,1]
mmax,flag = 0,0
used = [[[0] * M for _ in range(N)] for _ in range(H)] # 방문체크
for j in range(H): # tomato라는 변수에 3차원 정보 저장
arr = []
for i in range(N):
tmp = list(map(int,input().split()))
arr.append(tmp)
tomato.append(arr)
for k in range(H): # 완전탐색을 통해 초기 토마토 위치를 q에 저장
for j in range(N):
for i in range(M):
if tomato[k][j][i] == 1:
used[k][j][i] = 1
q.append([k,j,i])
def bfs():
global mmax,cnt
while q:
k,y,x = q.popleft()
for l in range(6):
dy = directy[l] + y
dx = directx[l] + x
dk = directk[l] + k
if dy >= N or dy < 0 or dx >= M or dx < 0 or dk >= H or dk < 0: # 배열 벗어나면 continue
continue
if tomato[dk][dy][dx] == -1: # 토마토가 없는 곳이라면 continue
continue
if used[dk][dy][dx] == 0: # 방문하지 않았던 곳이라면
used[dk][dy][dx] = 1 # 방문 체크 하고
tomato[dk][dy][dx] = tomato[k][y][x] + 1
if mmax < tomato[dk][dy][dx]:
mmax = tomato[dk][dy][dx]
q.append([dk,dy,dx]) # q에 추가
bfs()
for k in range(H): # bfs를 호출하고 난 후 다시 완전탐색으로 안익은 토마토 확인
for j in range(N):
for i in range(M):
if tomato[k][j][i] == 0:
flag = 1
if flag: # 안익은 토마토가 있다면
print(-1)
else:
if mmax == 0: # 처음부터 익은 토마토 밖에 없는 경우
print(0)
else:
print(mmax-1)
if else문을 반복해서 풀 수도 있겠지만 문제에서 원하는건 그게 아닌거같아서 BFS를 이용해 풀었다.
통로가 연결되어있는지 확인하는 방법은 가는 방향의 좌표에 1이나 -1의 부호를 바꾸고 도착하는 방향에 해당하는 좌표가 있는지 확인하면 된다.
예를들어 2번 터널 구조물 ( I )[[-1,0],[1,0]]과 그 아래 4번 터널 구조물 ( ㄴ ),[[-1,0],[0,1]]이 있다면 2번터널에서 아래방향으로가는 좌표 [1,0]에서 1의 부호를 바꾸어 [-1,0]으로 바꾸어주고 해당하는 좌표는 4번 터널 구조물의 좌표가 가지고 있으니 갈 수 있다고 판단한다
from collections import deque
def check(a,b,y,x):
if a[0] != 0: # 두 좌표중 1이나 -1의 부호를 바꿔줌
path = [-a[0],a[1]]
else:
path = [a[0],-a[1]]
if path in b: # 부호를 바꾼값이 도착지의 방향들중 하나와 같다면 갈 수 있음
used[dy][dx] = used[y][x] + 1
q.append([dy,dx,arr[dy][dx]])
def bfs(y,x,tmp):
global dy,dx,q
q = deque([(y,x,tmp)])
used[y][x] = 1
while q:
y,x,tmp = q.popleft()
for k in range(len(tunnel[tmp])): # tmp번 터널 구조물의 좌표의 수만큼 for문 돌리기
dy = tunnel[tmp][k][0] + y
dx = tunnel[tmp][k][1] + x
if dy >= N or dy < 0 or dx >= M or dx < 0: # 배열을 벗어나면 continue
continue
if arr[dy][dx] == 0 or used[dy][dx] != 0: # 길이 없거나, used배열을 확인해 갔던곳이라면 continue
continue
check(tunnel[tmp][k],tunnel[arr[dy][dx]],y,x) # 갈 수 있는 곳인지 확인하는 check함수 호출
# check( 가야 할 곳의 방향, 도착지의 방향들, 현재위치의 y좌표, 현재위치의 x좌표 )
TC = int(input())
for tc in range(1,TC+1):
N,M,Y,X,C = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(N)]
used = [[0] * M for _ in range(N)]
tunnel = [[[0]],[[-1,0],[1,0],[0,-1],[0,1]],[[1,0],[-1,0]],[[0,1],[0,-1]],[[-1,0],[0,1]],[[1,0],[0,1]],[[1,0],[0,-1]],[[-1,0],[0,-1]]]
# 각 터널 구조물의 좌표를 1번 index부터 3차원 배열로 저장
tmp,count = arr[Y][X],0
bfs(Y,X,tmp) # bfs(y좌표,x좌표,tmp번 터널 구조물)
for j in range(N):
for i in range(M):
if 0 < used[j][i] <= C: # bfs를 전부 돌고난 후 C시간 안에 갈 수 있는 공간만 확인
count += 1
print(f'#{tc} {count}')
import copy
def dfs(y,x,cnt,drill):
global K
tmp = arr[y][x] # 현재 위치를 tmp에 저장
for k in range(4): # 상하좌우로 이동
dy = directy[k] + y
dx = directx[k] + x
if dy >= N or dy < 0 or dx >= N or dx < 0: # 인덱스 배열 벗어나면 continue
continue
if used[dy][dx] == 1: # 이미 들렀던 곳이라면 contiunue
continue
if tmp <= arr[dy][dx] and drill == 0: # 지형의 높이가 높고 이미 등산로를 깎았으면 continue
continue
elif tmp <= arr[dy][dx] and drill == 1 and tmp > arr[dy][dx]-K:
# 가야할 곳의 지형의 높이가 높으면서, 등산로를 깎지 않았고, 깎았을 때 자신보다 높이가 낮아질수 있다면,
a = arr[dy][dx]
while True:
arr[dy][dx] -= 1 # 등산로를 1씩 깎다가 지나갈 수 있게되면 break
if tmp > arr[dy][dx]:
break
used[dy][dx] = 1
drill = 0
dfs(dy,dx,cnt+1,drill) # 드릴을 사용하고 그 위치로 dfs
drill = 1
used[dy][dx] = 0
arr[dy][dx] = a
elif tmp > arr[dy][dx]:
used[dy][dx] = 1
dfs(dy,dx,cnt+1,drill) # 지형이 낮다면 그 길로 진입
used[dy][dx] = 0
result.append(cnt) # dfs에서 탈출할 때의 cnt를 result에 저장
TC = int(input())
for tc in range(1,TC+1):
N,K = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(N)]
acc = copy.deepcopy(arr)
directy = [0,0,1,-1]
directx = [1,-1,0,0]
start,result = [],[]
st = 0
for j in range(N):
for i in range(N):
if arr[j][i] > st:
st = arr[j][i] # 1. 행렬의 가장 높은 봉우리의 높이를 구한다
for j in range(N):
for i in range(N):
if arr[j][i] == st:
start.append([j,i]) # 2. 봉우리의 좌표를 start에 저장
for i in range(len(start)): # 3. 가장 높은 봉우리를 돌 때 used초기화
used = [[0] * N for _ in range(N)]
arr = copy.deepcopy(acc)
used[start[i][0]][start[i][1]] = 1
dfs(start[i][0],start[i][1],1,1) # 4. dfs호출 (y좌표,x좌표,등산로의 길이,지형을 깍을 수 있는 횟수)
print(f'#{tc} {max(result)}') # 5. result에 저장된것중 가장 큰 값(가장 긴 등산로)출력
dfs와 bfs를 통한 완전탐색을 진행해서 시간과 메모리를 많이 사용했으나 다행히 pass
from collections import deque
import copy
TC = int(input())
for tc in range(1,TC+1):
N,W,H = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(H)]
combo = []
path = [''] * N
result = []
def dfs(level):
global combo,path
if level == N:
tmppath = copy.deepcopy(path)
combo.append(tmppath)
return
for i in range(W):
path[level] = i
dfs(level+1)
dfs(0) # 1. dfs를 통해 N개까지의 중복순열을 combo에 저장
def bfs(y,x):
global acc
q = deque([(y,x,acc[y][x])])
directy = [-1,1,0,0]
directx = [0,0,-1,1]
while q:
y,x,tmp = q.popleft() # 4. tmp에 acc 좌표의 값을 넣어줌
acc[y][x] = 0
for k in range(4):
dy = directy[k] + y
dx = directx[k] + x
for l in range(tmp-1): # 5. tmp만큼 상하좌우 이동하면서 벽을 부숨
if dy >= H or dy < 0 or dx >= W or dx < 0: # 5-1. 배열인덱스를 벗어나면 continue
continue
if acc[dy][dx] > 1: # 6. 벽을 부수는 길에 1 이상의 숫자가 있으면 ( 연쇄적으로 부술 수 있는 벽돌이 있다면 )
q.append([dy,dx,acc[dy][dx]]) # 6-1. q에 추가
acc[dy][dx] = 0
dy = directy[k] + dy
dx = directx[k] + dx
drop = [[0]*W for _ in range(H)] # 7. 벽을 부수고 난 후 drop이란 임시배열 초기화
for j in range(W):
tmpcnt = []
for i in range(H-1,-1,-1):
if acc[i][j] != 0: # 8. acc의 배열의 y축을 우선 돌며 값이 있다면 tmpcnt에 추가
tmpcnt.append(acc[i][j])
for i in range(H-1,-1,-1):
if tmpcnt == []:
break
drop[i][j] = tmpcnt.pop(0) # 9. drop 임시배열에 아래서부터 쌓아줌
acc = copy.deepcopy(drop) # 10. 배열을 새로 쌓은 후 drop을 acc에 깊은 복사를해줌
def crush(x): 3. 해당하는 y축에 벽돌이 있다면 bfs실행
global used
for j in range(H):
if acc[j][x] != 0:
bfs(j,x)
break
for j in range(len(combo)):
acc = copy.deepcopy(arr) # 2. acc 임시 배열을 계속 원상태로 복구시킴
for i in range(len(combo[j])):
crush(combo[j][i]) # 3. 구한 순열로 crush 함수 호출
cnt = 0
for jj in range(H):
for ii in range(W):
if acc[jj][ii] != 0:
cnt += 1 # 11. 순열을 한번 돌 때마다 벽돌의 수 확인
result.append(cnt)
print(f'#{tc} {min(result)}') # 12. 결과 값중 가장 작은 벽돌의 수를 출력
