9/30 코딩테스트 문제 풀이 (Softeer)🎈 순서대로 방문하기
첫 줄엔 격자 크기를 나타내는 n과 순서대로 방문해야 하는 칸의 수 m이 공백을 사이에 두고 주어진다. 두 번째 줄부터 n개의 줄에 걸쳐 각 행에 해당하는 n개의 수가 공백을 사이에 두고 주어진다. 0은 빈 칸을 1은 벽을 의미한다.
n+2부터 m개의 줄에 방문해야 할 m개의 칸의 위치 (x,y) 쌍이 공백을 사이에 두고 한 줄에 하나씩 순서대로 주어진다. 주어지는 칸에 벽이 있는 경우는 없고, 동일한 칸이 여러 번 주어지는 경우는 없다.
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
checkpoint = []
for _ in range(m):
x, y = map(int, input().split())
checkpoint.append([x-1, y-1])
visited = [[False]*n for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
cnt = 0
def dfs(start, depth):
global cnt
if start == checkpoint[depth]:
if depth == m-1:
cnt += 1
return
else:
depth += 1
x,y = start
visited[x][y] = True
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<=nx<n and 0<=ny<n and not visited[nx][ny] and graph[nx][ny]==0:
dfs([nx,ny], depth)
visited[x][y] = False
return
dfs(checkpoint[0], 1)
print(cnt)
< 풀이 과정 >
주어진 입력값들을 모두 처리 후 북남서동 4방향 탐색 진행
DFS 탐색으로 순서는 다음과 같다
1. 현 위치가 거쳐가야 할 위치인 경우 depth + 1, 만약 depth가 m-1와 일치한다면 cnt + 1하고 리턴
2. 현 위치 x,y 를 저장하고 방문 처리한 후 주어진 조건 일치하면 4방향 dfs 재귀탐색 진행.
3. 다음 번 탐색에도 사용되야 하므로 visited[x][y] = False로 정리 후 재풀이
🎈 강의실 배정
강의실 1개에 최대한 많은 강의를 배정하려 한다. 배정된 강의는 서로 겹치지 않아야 하고, 수업 시간 길이와 상관없이 최대한 많은 강의 배정하기.
import heapq
import sys
input = sys.stdin.readline
n = int(input())
time = []
for _ in range(n):
s,e = map(int, input().split())
heapq.heappush(time, (e, s))
answer = 0
init = 0
while time:
a, b = heapq.heappop(time)
if b >= init:
init = a
answer += 1
print(answer)< 풀이 과정 >
강의실은 1개로 고정된 상황에서 최대한 많은 강의를 넣는 방법을 구하는 문제.
결국 현재 고른 강의의 끝나는 시점이 시작 시점과 같거나 큰지 여부를 확인해주어야 한다.
우선 주어진 제약 조건을 보아 우선순위 큐를 사용해서 해결해 주어야 한다.
- heap 구조인 time 배열에 (끝나는 시각, 시작 시각)을 입력하여 끝나는 시각을 기준으로 오름차순 정렬한다.
- time 힙 배열을 a,b를 순차적으로 꺼내되, 현재 강의의 시작시간을 init으로 변경해주고 다음 강의 시작을 b로 두어 비교해가며 answer를 1씩 늘려준다.
🎈 자동차 테스트
3대의 자동차를 테스트해 주어진 각 연비의 중앙값이 실제 주어진 중앙값 리스트와 일치하는 개수를 구하는 문제.
입력형식은 다음과 같다.
- 첫 줄에 n,q가 공백을 사이에 두고 주어진다.
- 두번째 줄에는 n개의 자동차의 연비에 해당하는 값이 공백을 두고 주어진다.
- 세번째 줄부터 q개의 줄에 걸쳐 중앙값이 주어진다.
-> q개의 줄에 걸쳐 3대의 자동차를 골랐을 때 연비의 중앙값이 나오는 서로 다른 가짓수를 구하는 문제.
🎈 Garage Game
게임의 룰은 가로 세로 N칸의 차고가 있고 각 차고에는 색깔이 있는 자동차가 하나씩 있다. 한 턴에 한 칸을 선택하며, 선택한 칸과 상하좌우 칸에 들어있는 자동차의 색이 같으면 모두 사라진다. 그리고 사라진 칸들과 연결된 칸들의 상하좌우 칸에 들어있는 자동차의 색이 같다면 함께 사라진다.
이때 획득가능한 점수는 사라진 자동차의 개수와 사라지는 차고 칸을 모두 포함하는 가장 작은 직사각형의 넓이의 합이다.
자동차들이 사라지고 나면 위에 있는 자동차들이 아래로 떨어져 빈 칸을 채운다. 위쪽에는 충분한 자동차들이 더 있어 추가적으로 떨어지며 모든 칸을 채운다.
자동차가 어떤 것이 떨어질지 입력이 주어지고 위와 같은 게임을 3차례 반복했을 때 얻을 수 있는 가장 큰 점수를 계산하는 문제.
해결 필요..!
