https://www.acmicpc.net/problem/9663
이거 분명히 전에 풀었었는데 기억 안나죠?
복습은 정말 중요하다....
심지어 이게 어떤 유형인지 알아내는것도 힘들었다
좌표 하나하나 찍다가 그냥 구글링했다,,,ㅎㅎ
N-Queen은 백트래킹의 대표적인 예제인데, 체스에서 퀸은 가로 세로 대각선으로 범위 제한 없이 이동할 수 있다.
따라서 한 행당 한 개의 퀸만 존재할 수 있으므로 굳이 NxN 배열을 만들 필요 없이 1차원 배열로 표현할 수 있다!
ex) 첫 번째 행에 퀸이 3열에 있다고 하면, col[0]에 3을 저장한다.
여기서 같은 행, 열, 대각선에 있는지 비교하면 되는데
- 이미 한 행에 하나의 퀸만 있다고 가정했으니 같은 행일 때는 비교하지 않음
- 같은 열일 때 : col[i] == col[depth]일 때
- 대각선상에 있을 때 : abs(depth - i) == abs(col[depth] - col[i])
-> x좌표끼리, y좌표끼리 뺄셈을 했을 때 절댓값이 같은 숫자가 나오면 대각선상에 있음
ex) (x,y)와 (x+n, y+n)에 퀸이 있다고 했을 때,
x-(x+n) = y-(y+n) = -n
그리고 퀸을 놓을 수 없다고 판단되면 백트래킹을 수행한다.
(퀸을 놓을 수 없다면 더 진행하지 않고 그 전 단계로 돌아가 다른 루트를 진행한다.)
# 9663 N-Queen
# 백트래킹
# 구글링했습니다...
n = int(input())
col = [0] * n
result = 0
def check(depth):
# 퀸을 놓을 수 있는지 검사
for j in range(depth):
if col[depth] == col[j]:
return False
elif abs(depth - j) == abs(col[depth] - col[j]):
return False
return True
def nqueen(depth):
global result
if depth == n:
result += 1
return
for i in range(n):
col[depth] = i
if check(depth):
nqueen(depth+1)
nqueen(0)
print(result)
python3로는 시간초과 떴고, pypy3로 통과했다
그리고 파이썬에서는 자동으로 전역변수 선언이 안 되기 때문에 (배열 제외) 전역변수를 쓰고싶으면 함수 안에서 global로 불러온 뒤 써야 한다
https://www.acmicpc.net/problem/14502
문제를 보고 3187 양치기 꿍 문제가 생각났는데, 알고리즘 분류를 보니 bfs로 푸는 게 맞았다.
문제는 그 이후에 어떻게 풀어야 할 지 모르겠다는 거다...
벽을 도대체 어떤 기준으로 세워야 하는 건지 감이 안 잡혀서 구글링했는데
그냥 빈칸이면 냅다 벽을 세우고 모든 경우의 수를 계산해야 하는 거였다
(입력받는 연구소 크기가 작아서 이렇게 다 계산해도 된다고 함..)
- 빈 칸을 발견하면 벽을 세워본다. (이 때 지도를 복사해서 써야함.. 다양한 경우를 확인하는 거기 때문에!!)
- 이어서 벽을 2개 더 무작위로 세워본다
- 벽 3개를 다 세웠으면 그 상태로 바이러스를 퍼뜨려본다 (bfs)
- 바이러스를 퍼뜨린 후 안전 영역을 센다
- 최댓값을 비교해가며 result에 저장한다
- 1번으로 돌아가서 벽을 다시 허문다 -> 반복
- 마지막으로 결과값 출력
처음에 자꾸 결과값이 0이 나와서 왜지?? 했는데 얕은 복사를 써서 그랬다....
이 때 알았다 append가 얕은 복사였다는 걸,,
파이썬에서는 deepcopy 라이브러리를 제공해주니까 넙죽 받아 쓰면 된다
# 14502 연구소
import sys
import copy
from collections import deque
n, m = map(int, sys.stdin.readline().split())
arr = [] # 연구소 지도
virus = [] # 바이러스의 위치를 저장할 배열
temp = [] # 벽을 세우고 허물 때 쓸 임시 지도 배열
# 상하좌우 이동
dx = [0, 0, 1, -1]
dy = [-1, 1, 0, 0]
# 결과값
result = 0
# 연구소 지도 입력
for i in range(n):
tmp = list(map(int, sys.stdin.readline().split()))
# 바이러스의 위치 저장
for j in range(m):
if tmp[j] == 2:
virus.append([i, j])
arr.append(tmp)
# 바이러스 퍼뜨리기
def spread_virus():
lab = copy.deepcopy(temp) # 지도 복사
q = deque(virus) # 바이러스 위치 큐 삽입
# bfs
while q:
y, x = q.popleft() # 바이러스 위치 pop
# 상하좌우 이동
for _ in range(4):
nextY = y + dy[_]
nextX = x + dx[_]
if 0 <= nextY < n and 0 <= nextX < m: # 범위 내
if lab[nextY][nextX] == 0: # 빈 칸이면
lab[nextY][nextX] = 2 # 바이러스 감염
q.append([nextY, nextX]) # 바이러스 큐에 추가
zero = 0
# 안전영역(빈 칸) 세기
for _ in range(n):
zero += lab[_].count(0)
# 더 큰 안전 영역의 넓이 저장
global result
result = max(result, zero)
return
# 벽 세우기
# cnt : 벽의 개수
def make_wall(cnt):
# 벽을 다 세웠으면 바이러스 퍼뜨려보기
if cnt == 3:
spread_virus()
return
# 벽 3개를 다 안 세웠을 때
for k in range(n):
for p in range(m):
if temp[k][p] == 0: # 빈칸을 발견하면
temp[k][p] = 1 # 해당 칸에 벽을 세움
make_wall(cnt+1) # 이어서 벽 세우기
temp[k][p] = 0 # 해당 칸에 벽을 다시 허문다
for i in range(n):
for j in range(m):
if arr[i][j] == 0: # 빈칸을 발견하면
temp = copy.deepcopy(arr) # 지도 복사
temp[i][j] = 1 # 해당 칸에 벽을 세움
make_wall(1) # 이어서 벽 세우기
temp[i][j] = 0 # 해당 칸에 벽을 다시 허문다
print(result)
그냥 돌려봐도 너무 오래 걸려서 python3으로 제출할 엄두도 못 냈다
pypy3로 제출해서 통과!!
https://www.acmicpc.net/problem/1753
보자마자 어? 이거 분명히..비슷한 유형을 전에 풀었을텐데? 라는 생각이 들었다
하지만 당연하게도 시간이 흘러 까먹었기 때문에... 책을 다시 읽었다
책 예제를 참고하여 다익스트라 알고리즘으로 풀었다.
매번 가장 최단 경로의 정점을 선택해야 하기 때문에 heapq를 이용했다
# 1753 최단경로
import sys
import heapq
INF = int(1e9) # 무한을 의미하는 변수
# 정점의 개수 v와 간선의 개수 e 입력
V, E = map(int, sys.stdin.readline().split())
# 시작 정점의 번호 입력
start = int(input())
# 연결리스트
graph = [[] for i in range(V + 1)]
# 최단 거리 테이블
distance = [INF] * (V + 1)
# 연결 정보 입력
for i in range(E):
# u에서 v로 가는 가중치 w인 간선이 존재
u, v, w = map(int, sys.stdin.readline().split())
graph[u].append([v, w])
def dijkstra(s):
q = []
# (가중치, 정점) 큐에 삽입
heapq.heappush(q, (0, s))
distance[s] = 0
while q:
dist, now = heapq.heappop(q)
# 이미 방문한 노드일 경우 continue
if distance[now] < dist:
continue
# 현재 노드의 인접 정점 확인
for i in graph[now]:
cost = dist + i[1]
if cost < distance[i[0]]:
distance[i[0]] = cost
heapq.heappush(q, [cost, i[0]])
dijkstra(start)
for i in range(1, V + 1):
if distance[i] == INF:
print("INF")
else:
print(distance[i])
이번 주 스터디 후기 : 골드는 골드구나...
이거 분명히 전에 풀었었는데 기억 안나죠? 골드는 골드구나...
-> your 맘 = my 맘