1. 각 방에는 여러 개의 스위치가 있습니다. 따라서 매트릭스를 만들어서 다른 방의 스위치 좌표들을 저장합니다
위 입력을 토대로 한 예시 매트릭스입니다. 이 매트릭스는 switchs라고 부르겠습니다.
2. 스위치의 상태(on/off)와 베스가 이동 가능한 방인지를 표현할 매트릭스를 만듭니다.
이 매트릭스는 board라고 부르겠습니다.
불이 꺼진 상태 : 0
불이 켜진 상태 : 1
베스가 이동 가능한 방 : 2
베스는 항상 (1, 1)에서 출발한다고 했으므로, (1, 1)의 초기값은 2입니다.
3. 베스의 출발 지점인 (1, 1)을 queue 리스트에 담습니다.
- queue 리스트에 들어 있는 좌표는 다른 방의 스위치를 탐색하기 위해 사용됩니다.
- queue에 리스트에 값이 없어질 때 까지 4 ~ 4-2-1 과정에 대한 반복문이 수행됩니다.
4. queue에 있는 좌표 (1, 1)을 빼내고, 해당 좌표의 switchs 매트릭스에 있는 모든 다른 방의 스위치를 누릅니다.
- 스위치를 켠 방의 상하좌우를 탐색하여 주변에 2가 있는지 확인합니다.
4-1. 주변에 2가 없다면 board 매트릭스의 해당 좌표에 1을 입력합니다.
(불만 켭니다 : 해당 방에는 베스가 들어갈 수 없습니다.)
4-2. 주변에 2가 있다면 board 매트릭스의 해당 좌표에 2를 입력합니다.
(불이 켜져 있는 인접한 방이므로, 베스가 들어갈 수 있습니다.)
- 주변에 1이 남아 있는 경우를 고려하여, 다시 한 번 상하좌우를 탐색해야 합니다
4-2-1. 상하좌우로 인접한 방에 1이 있는지 확인한 후, 존재한다면 2로 수정합니다.
- 4-2-1번 작업은 BFS 알고리즘이 재귀적으로 수행되어야 합니다.
- 2로 수정된 방의 좌표에서는 switchs에 기록된 정보들의 탐색이 이뤄지지 않았으므로, queue에 담습니다.
* 4-2-1 작업이 재귀적으로 수행되어야 하는 이유
첫 번째 그림은, 기존에 불 켜져있는 방들이 밀집됐지만, 베스가 들어갈 수 없는 방을 표현했습니다.
두 번째 그림에서 (1, 2)에 불이 켜짐으로써 나머지 (2, 2), (3, 2), (3, 3)도 들어갈 수 있는 방으로 변해야 하는 상황이 되었습니다. 따라서 4-2-1 작업은 재귀적으로 수행되어야 합니다. 그 결과는 세 번째 그림과 같습니다.
코드
import sys
from collections import deque
# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")
n, m = map(int, input().split()) # n : n x n의 방을 만듦, m : m개의 데이터를 받음
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
board = [[0] * (n+1) for _ in range(n+1)] # 1: 불 켜짐, 2: 이동 가능
board[1][1] = 2
switchs = [[[] for _ in range(n+1)] for _ in range(n+1)]
for _ in range(m):
x, y, a, b = map(int, input().split())
switchs[x][y].append([a, b])
def BFS(x, y):
for i in range(4):
xx = x + dx[i]
yy = y + dy[i]
if 0 < xx <= n and 0 < yy <= n:
if board[xx][yy] == 1:
board[xx][yy] = 2
queue.append([xx, yy])
BFS(xx, yy)
cnt = 1
queue = deque([[1, 1]])
while queue:
x, y = queue.popleft()
for a, b in switchs[x][y]:
for i in range(4):
aa = a + dx[i]
bb = b + dy[i]
if 0 < aa <= n and 0 < bb <= n:
if board[a][b] == 2:
break
if board[aa][bb] == 2:
cnt += 1
board[a][b] = 2
queue.append([a, b])
BFS(a, b)
break
if board[a][b] == 0:
board[a][b] = 1
cnt += 1
print(cnt)
- eval : string으로 주어진 수식에서 숫자와 부호를 구분하여 계산합니다. 결과 값은 int로 리턴됩니다.
코드
import sys
# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")
def calculator(form):
form = form.replace(" ", '')
return eval(form)
def DFS(L, form):
if L == n:
tot = calculator(str(form))
if tot == 0:
print(form)
return
else:
for x in [' ', '+', '-']:
transform = str(form) + x + str(r[L+1])
DFS(L+1, transform)
if __name__ == "__main__":
t = int(input())
for _ in range(t):
n = int(input())
r = list(range(n+1))
DFS(1, 1)
print()
1. 학생들이 제출한 목록을 "b를 기준으로 오름차순 --> a를 기준으로 내림차순" 한다.
2. 책의 분배 상태를 의미하는 리스트를 한 개 만든다.
- 인덱스는 책의 번호를 의미한다.
- 인덱스 값은 책을 분배했음(1), 분배하지 않음(0)을 의미한다.
3. 학생들이 제출한 범위 내에서 반복문을 진행하고, 책의 분배 상태를 확인한다.
- 분배되지 않은 책을 발견하면, 리스트의 해당 인덱스를 1로 변경한 후 반복문을 종료한다.
* b를 기준으로 오름차순 한 이유
[1, 2]와 [2, 4]의 예제가 존재한다고 가정하자.앞선 학생이 갖는 선택지는 1과 2가 있다.뒷 학생이 갖는 선택지는 2, 3, 4가 있다.
만약 앞선 학생이 1번 책을 선택한다면, 뒷 학생은 온전히 2, 3, 4의 선택지를 갖게 된다.
하지만 만약 앞선 학생이 2번 책을 선택한다면, 뒷 학생은 3, 4의 선택지를 갖게 된다.
또한, [a, b]에서 b는 언제나 a보다 작거나 같다. (a<=b)
따라서 b가 낮은 학생들이 우선순위를 가져야 한다.
* a를 기준으로 내림차순 한 이유
b를 기준으로 오름차순한 상태에서 a를 기준으로 내림차순 한 이유는 다음과 같다.
예를 들어, [2, 3]과 [1, 3]이 존재한다고 하자.
앞선 학생의 경우의 선택지는 2와 3이 있다.
반면에 뒷 학생의 선택지는 1, 2, 3이 있다.
따라서 선택지가 더 적은 [2, 3]을 제출한 학생이 우선순위를 가져야 한다.
즉, a를 기준으로 내림차순 해야 한다.
코드
import sys
# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")
n = int(input())
for _ in range(n):
numBooks, numStudents = map(int, input().split())
queue = [list(map(int, input().split())) for _ in range(numStudents)]
queue.sort(key=lambda x: x[1])
status = [0] * (numBooks+1)
for i in range(numStudents):
for j in range(queue[i][0], queue[i][1]+1):
if status[j] == 0:
status[j] = 1
break
print(sum(status))
1. 3차원 배열에서의 BFS만 구현하면 된다. (기본 2차원 배열에서 배열을 하나 더 추가한 것이다.)
1. 익은 토마토의 좌표를 리스트에 담는다.
2. 익은 토마토를 중심으로 상/하/좌/우/위/아래로 좌표를 이동시킨다.
3. 이동한 좌표가 좌표평면에서 벗어나지 않는다면 계속 진행한다.
4. 이동 전 익은 토마토의 좌표의 값에 1을 더하여 이동 후의 좌표 평면에 1을 더해준다. (매일 주변에 있는 토마토가 익으므로, 좌표평면에 존재하는 값은 "지난 일수"를 의미 한다.)
5. 좌표를 이동함으로써 익게 된 토마토의 좌표를 리스트에 담는다.
6. x, y, z 방향으로 3중 반복문을 실행하여 토마토가 전부 익었는지 확인한다.
- 모두 익지 않았다면 -1을 출력하고 프로그램을 종료한다.
7. 최대 값(mx)을 1로 초기화한다.
- 문제 조건에서 처음부터 토마토가 모두 익었으면 0을 출력하라고 했다.
8. x, y, z 방향으로 3중 반복문을 실행하여, mx와 비교하며 좌표 평면에서 가장 큰 수(익는데 걸린 일수)를 찾는다.
9. mx - 1을 해서 정답을 출력한다.
- 시작 시에 좌표평면의 값이 1이므로, 익는데 걸린 시간에 포함시키지 않는다.
코드
import sys
from collections import deque
# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")
def BFS():
while queue:
x, y, z = queue.popleft()
for dx, dy, dz in mv:
xx = x + dx
yy = y + dy
zz = z + dz
if 0 <= xx < col and 0 <= yy < row and 0 <= zz < height and board[zz][yy][xx] == 0:
board[zz][yy][xx] = board[z][y][x] + 1
queue.append([xx, yy, zz])
if __name__ == '__main__':
col, row, height = map(int, input().split())
board = [[list(map(int, input().split())) for _ in range(row)] for _ in range(height)]
mv = ((1, 0, 0), (-1, 0, 0), (0, 1, 0), (0, -1, 0), (0, 0, 1), (0, 0, -1))
# 익은 것의 좌표를 찾는다.
queue = deque()
for y in range(row):
for x in range(col):
for z in range(height):
if board[z][y][x] == 1:
queue.append([x, y, z])
BFS()
# 모두 다 익었는지 확인한다.
for y in range(row):
for x in range(col):
for z in range(height):
if board[z][y][x] == 0:
print(-1)
sys.exit()
# 걸린 일수를 출력한다.
mx = 1
for z in range(height):
for y in range(row):
mx = max(mx, max(board[z][y]))
print(mx-1)
이런 경우에는 5kg짜리 봉투를 2개를 사용한 뒤에 나머지를 3kg짜리 봉투에 담아야 합니다.
그렇게 되면 3kg짜리 봉투에 들어갈 수 있는 설탕의 양은 2kg 밖에 되지 않습니다.
즉, 문제에서 요구하는 답을 낼 수 없습니다.
5kg짜리 봉투 1개에만 적당히 소금을 담고, 3kg짜리 봉투를 2개를 사용하여 설탕을 담으면 문제에서 요구하는 정답을 제출할 수 있습니다.
알고리즘
N이 11로 주어진 상황을 가정하고 설명하겠습니다.
1. 5kg짜리 봉투가 허용하는 최대 무게부터 5 단위로 감소시키며, 0까지 반복문을 실행합니다.
2. N에서 5가 허용하는 무게(10, 5, 0)를 뺍니다.
뺀 값은 다시 N에 담습니다.
3. N을 3으로 나눕니다. 이 때 나머지가 0이면, 반복문을 빠져나옵니다.
4. 답으로는 5의 "'배수(2)'가 되는 값 + N/3의 몫"으로 제출합니다. (나머지가 0인 것이 없다면 -1을 답으로 제출합니다)
코드
import sys
# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")
inputData = int(input())
T = inputData//5
answer = -1
for i in range(T, -1, -1):
n = inputData - (5 * i)
a, b = divmod(n, 3)
if b == 0:
answer = i + a
break
print(answer)
- 스도쿠의 각 칸에는 가로/세로/ 3 x 3 박스 내에 1~9까지 곂치는 수가 존재하지 않아야 한다.
본 문제를 풀이할 때 주의사항이 있다.
"가로/세로/ 3 x 3 박스 내에 1~9까지 곂치는 수"를 고려하여 문제를 풀었을 때 답이 나오지 않는 경우가 존재한다.
그럴 때는 이전 칸으로 돌아가서 조건에 맞는 다른 수로 수정해야 한다.
따라서 이 문제는 백 트래킹을 사용해야 한다.
알고리즘
1. 스도쿠에 빈 공간(0)이 있는지 확인한다.
2. 빈 공간이 없으면 스도쿠가 완성됐으므로 종료한다.
3. 빈 공간이 있으면 빈 공간(col, row)이 어딘지 말한다.
4. 빈 공간에 어떤 값(1~9)이 들어갈 수 있는지 탐색한다.
- 찾았다면 스도쿠에 채워넣는다.
- 채워넣을 수 있는 게 없다면 백 트래킹 한다.
스도쿠에 빈 공간 확인하기
1. 스도쿠 전체를 탐색하며 빈 공간(0)이 발견되면 해당 좌표를 리턴한다.
2. 스도쿠에서 빈 공간이 발견되지 않으면, None을 리턴한다.
빈 공간에 들어갈 수 있는 값인지 식별하기
빈 공간에 들어갈 수 있는 값인지 식별하기 위해서는 "가로 / 세로 / 3 x 3 박스"를 탐색해야 한다.
1. 가로 탐색
스도쿠의 column을 고정시키고 row 방향으로 이동 탐색을 진행한다.
들어가고자 하는 값이 발견되면 False를 리턴한다.
2. 세로 탐색
스도쿠의 row을 고정시키고 col 방향으로 이동 탐색을 진행한다.
들어가고자 하는 값이 발견되면 False를 리턴한다.
3. 3 x 3 박스 탐색
1. 탐색이 시작될 지점을 계산한다
2. 탐색시작 지점에서부터 3 x 3 지점을 탐색한다.
1. (7, 4) 지점이 속한 박스 영역의 시작 지점을 찾는다고 가정하자.
2. 왼쪽 그림의 경우 박스의 시작 지점은 (6, 3)이다.
3. 박스 영역의 시작 지점을 찾는 공식은 (컬럼좌표//3 * 3, 로우좌표//3 *3)이다.
("a//b"는 a와 b를 나눴을 때 몫과 나머지 중에 몫만 출력한다)
코드
import sys
# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")
def pretty_print():
for i in range(9):
for j in range(9):
print(board[i][j], end='')
print()
def find_empty():
for i in range(9):
for j in range(9):
if board[i][j] == 0:
return i, j
return None, None
def valid(col, row, val):
# 가로 축 점검
for i in range(9):
if board[col][i] == val:
return False
# 세로 축 점검
for i in range(9):
if board[i][row] == val:
return False
# 3x3 박스 점검
box_col = col // 3 * 3
box_row = row // 3 * 3
for i in range(3):
for j in range(3):
if board[box_col+i][box_row+j] == val:
return False
return True
def solution():
col, row = find_empty()
if col is None:
return True
else:
for i in range(1, 10):
if valid(col, row, i):
board[col][row] = i
if solution():
return True
board[col][row] = 0
return False
if __name__ == '__main__':
board = [list(map(int, input())) for _ in range(9)]
solution()
pretty_print()
import sys
# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")
def passOrNot(v, usedIdx):
global mn
for i in range(4):
if req[i] > v[i]:
return False
mn = v[4]
mnIdx.clear()
mnIdx.extend(usedIdx)
return
def DFS(L, v, usedIdx):
global mn
if v[4] >= mn:
return
if passOrNot(v, usedIdx):
return
if L == n:
return
else:
usedIdx.append(L+1)
for i in range(5):
v[i] += data[L][i]
DFS(L + 1, v, usedIdx)
usedIdx.pop()
for i in range(5):
v[i] -= data[L][i]
DFS(L + 1, v, usedIdx)
if __name__ =='__main__':
n = int(input())
req = list(map(int, input().split()))
data = [list(map(int, input().split())) for i in range(n)]
mn = 9999999
mnIdx = []
res = DFS(0, [0]*5, [])
if mn == 9999999:
print(-1)
else:
print(mn)
for i in mnIdx:
print(i, end=' ')
