골드
너무..
너무...........
어렵다 ㄱ-

#9663 N-Queen

🔗https://www.acmicpc.net/problem/9663

생각

8-Queen 에서 해를 탐색하는 과정을 애니메이션화 한 것.
이거를 보고 아! 백트래킹같다. 라고 생각은 했는데
문제는 백트래킹을 어떻게 구현해야하는가... 를 모르겠어서
검색 시작

구현

백트래킹은 dfs로 구현 가능하다.
queen 배열을 통해 각 행의 몇번째 자리에 퀸이 놓였는지 저장 후,
check 함수를 통해 queen 배열을 돌면서
다음 노드가 유망한지 검사한다 (이전에 놓여진 퀸과 같은 열에 있는가, 대각선상에 있는가를 검사함)
이후 유망하다고 판단된 노드만 dfs()를 실행한다.

코드 (PyPy3)

import sys

n=int(sys.stdin.readline().rstrip())

queen=[0]*n

def check(y):
    for i in range(y):
        if queen[y]==queen[i] or abs(queen[i]-queen[y])==y-i:
            return False
    return True

def dfs(y):
    global result
    if y>=n:
        result+=1
        return
    for i in range(n):
        queen[y]=i
        if check(y):
            dfs(y+1)
                
result = 0 
dfs(0)

print(result)

#14502 연구소

🔗https://www.acmicpc.net/problem/14502

생각

와이씨..
어렵다

처음 든 생각

1.벽을 세울 수 있는 경우의 수를 모두 구함
2.해당 경우를 모두 bfs를 통해 바이러스를 퍼뜨린다음
3.0의 개수(안전영역의 크기) 를 구함
4.안전영역의 최대 크기 출력

구현

바이러스 퍼뜨리는건 bfs로 쉽게 구현 가능했는데
벽을 세우는거가 조금 어려웠다..
처음에는 삼중 for문으로 해야되나? 싶었는데(세워야 되는 벽이 세개니까)
감이 안와서.. 검색을 해보니
그래프를 탐색하며, 해당 칸이 0일때 벽을 세워주고, 이후 세운 벽의 개수(cnt)를 인자로 계속 넘겨주며 재귀함수를 실행, cnt가 3일때 bfs를 실행하고 멈추는 코드를 발견.
해당 방식을 참고해 작성했음

코드 (PyPy3)

from collections import deque
import sys
import copy

n,m = map(int, sys.stdin.readline().split())

graph=[]
for i in range(n):
    graph.append(list(map(int,sys.stdin.readline().split())))

dx=[-1,1,0,0]
dy=[0,0,-1,1]

max_result=0

def bfs():
    global max_result
    
    tmp=copy.deepcopy(graph)
    result=0
    que=deque()
    
    for i in range(n):
        for j in range(m):
            if tmp[i][j]==2:
                que.append([i,j])
                
    #바이러스 퍼뜨리기
    while que:
        x,y=que.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            
            if nx<n and ny<m and nx>=0 and ny>=0:
                if tmp[nx][ny]==0:
                    tmp[nx][ny]=2
                    que.append([nx,ny])

    #최대값 갱신
    for t in tmp:
        result+=t.count(0)
    max_result=max(max_result,result)

#벽을 짓는다
def build(cnt):
    if cnt == 3:
        bfs()
        return
    for i in range(n):
        for j in range(m):
            if graph[i][j]==0:
                graph[i][j]=1
                build(cnt+1)
                graph[i][j]=0

build(0)
print(max_result)

#1753 최단경로

🔗https://www.acmicpc.net/problem/1753

생각

일단 가중치를 가진 인접리스트를 작성해야겠다!!
그리고 최단경로를 찾는 알고리즘을 적용하면 되겠다!
하고 교재를 살펴봤더니 다익스트라 알고리즘이 있어서 해당 코드를 참고하였다.

코드

import heapq
import sys
INF=int(1e9)

#v 정점의 개수 e 간선의 개수
v,e=map(int, sys.stdin.readline().split())
#k 시작 정점의 번호
k=int(sys.stdin.readline().rstrip())

#인접리스트
adj=[[] for _ in range(v+1)]
#최단거리 테이블 (무한대로 초기화)
distance=[INF]*(v+1)

#인접리스트 작성
for i in range(e):
    a,b,c=map(int,sys.stdin.readline().split())
    adj[a].append((b,c))

def dijkstra(start):
    q=[]
    heapq.heappush(q,(0,start))
    distance[start]=0
    while q:
        dist, now = heapq.heappop(q) #dist: 가중치 now:노드
        if distance[now]<dist:
            continue
        for i in adj[now]:
            cost=dist+i[1]
            #최단거리 테이블 갱신
            if cost<distance[i[0]]:
                distance[i[0]]=cost
                heapq.heappush(q,(cost,i[0]))

dijkstra(k)

for i in range(1,v+1):
    if distance[i]==INF:
        print("INF")
    else:
        print(distance[i])