Coding 공부

from itertools import combinations
from collections import deque
def bfs(active_virus,total_virus):
    global result,virus_list,N
    virus_cnt = 0
    deactive_virus = virus_list-active_virus
    stack = deque()
    spend_time = [row[:] for row in spend_time_stand]
    for x,y in active_virus:
        stack.append((x,y,0))
        spend_time[x][y] = 0
        virus_cnt += 1
    min_time = -1
    while stack:
        x,y,time = stack.popleft()
        if min_time > result:
            return
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<N and 0<=ny<N:
                if spend_time[nx][ny] == -1 and (nx,ny) not in wall_list:
                    if (nx,ny) not in deactive_virus:
                        spend_time[nx][ny] = time+1
                        stack.append((nx,ny,time+1))
                        min_time = spend_time[nx][ny]
                        virus_cnt += 1
                    else:
                        spend_time[nx][ny] = 0
                        stack.append((nx,ny,time+1))
                        

        
    if total_virus == virus_cnt:
        if result >min_time and min_time != -1:
            result = min_time


    



N,M = map(int,input().split())
dx = [-1,1,0,0]
dy = [0,0,1,-1]
arr = [list(map(int,input().split())) for _ in range(N)]
virus_list = set()
wall_list = set()
total_virus = N*N
spend_time_stand = [[-1] *N for _ in range(N)]
for x in range(N):
    for y in range(N):
        if arr[x][y] == 2:
            virus_list.add((x,y))
        elif arr[x][y] == 1:
            wall_list.add((x,y))
            total_virus -= 1

start_virus_list = combinations(virus_list,M)
result = float('inf')
if total_virus-len(virus_list)+M != M:
    for lists in start_virus_list:
        bfs(set(lists),total_virus-len(virus_list)+M)
else:
    result = 0

if result == float('inf'):
    print(-1)
else:
    print(result)

연구소 시리즈 문제 중 3번 문제이다. 여기서는 예외로 해야할 곳이 생각외로 많아서 많이 틀리면서 푼 문제이다.

문제 자체를 이해하자면, 처음부터 있는 바이러스들이 존재한다.

그런데 여기서 M개의 바이러스가 활성화 되고, 나머지 바이러스는 비활성 상태가 된다.

활성 바이러스가 비활성 바이러스 가면 활성화 상태가 된다.

여기서 주의해야할 점은 이 점이다. 처음부터 있는 바이러스는 비활성 상태지만 이미 뿌려진 상태이기 때문에, 비활성->활성이 될뿐이지, 이미 바이러스가 존재하기 때문에, 퍼트리는데 드는 시간에는 포함이 되지 않는다.

그리고 두번째로 주의해야할 점은, 퍼트리는데 드는시간에 들지는 않지만, 비활성간을 활성화시키고 넘어가기 위해선 시간이 누적되는 것이다.

예를 들어 

활성 비활성 비활성 빈칸

이렇게 되어있을시, 

1초 뒤

활성 활성 비활성 빈칸

2초뒤

활성 활성 활성 빈칸

3초뒤

활성 활성 활성 활성

이렇게 3초가 걸리는 걸 알 수 있다. 비활성 바이러스는 이미 존재하던 바이러스이기 때문에 새로 퍼트린 바이러스 시간에는 포함되지 않지만, 이동통로로서는 역할을 하기 위해 시간은 지나가줘야한다.

인제 코드로 돌아가서 기본적인 원리는 연구소 문제들과 동일하다.

전체에 바이러스가 퍼트릴수 있는 최소시간을 구하는 것이고, 구하기 전에 전처리 과정을 해준다.

먼저 벽인 부분은 따로 wall_list로 저장해두고, 전체 바이러스가 생길수 있는 공간 N*N에서 1씩 빼준다.

왜냐하면 벽에는 바이러스가 못살기 때문이다.

또한 virus가 존재하는 경우엔, virus_list라는 set에 저장해두었다.

만약 바이러스가 생길수 있는 공간에서 입력된 바이러스의 값을 뺐을때 0이면, 이미 전부 퍼진거니 0을 출력해주면 된다.

그렇지 않을 경우, 바이러스를 퍼트리는 과정을 해준다. 앞에서 virus_list에서 M개의 combination을 뽑아낸다.

퍼지는 시간이 들어갈 주어진 공간과 같은 크기의 행렬을 만들어준다. 또한, 기본값은 -1로 시간상 존재할수 없는 값으로 초기화 해준다.

파이썬의 집합의 특징을 이용해 전체 virus_list에서 active_list(활성화된 바이러스)를 빼주어서, 비활성된 바이러스의 집합을 따로 만들어준다.

그리고 우리가 만든 spend_time이라는 행렬에 활성화된 바이러스의 위치에 0으로 초기화 시켜주고 stack에 넣어준다.

나머지는 기본적인 bfs랑 동일하다.

여기서 주의해야할 점은 deactive_virus인 공간과 빈공간에서 차이점을 둔다.

deactive_virus는 stack에 똑같이 time을 +1 해서 추가해주는 대신 spend_time은 0으로 해준다.

하지만 빈공간일때는 spend_time에 현재시간 +1 을 넣어주고, stack에도 동일하게 넣어준다. 그리고 virus_cnt를 늘려준다.

그리고 여기서 min_time을 갱신시켜준다. bfs는 최단경로를 구하는 것이기 때문에, 가장 마지막에 stack에 들어간 값이 모두 퍼트리는데 걸리는 시간이기 때문이다.

또한 시간을 줄여보고자, 우리가 출력하고자하는 결과 result보다 현재 min_time이 높으면 bfs를 중단시켜주었다.

이 문제에서 여러번 시도하면서 틀렸던 점은 위의 주의점 2가지를 빠르게 파악을 못했기 때문이었다. 문제를 제대로 이해하는데, 더 열심히 해야겠다.

이 문제를 풀면서 틀렸습니다. 됬을때 도움이 되는 반례는

5 1

2 1 1 1 1

2 1 1 1 1

2 1 1 1 1

2 1 1 1 1

2 1 1 1 1

answer = 0

4 2

0 1 1 0

2 1 1 2

2 1 1 2

0 1 1 0

answer = 2

더 많은 반례는 www.acmicpc.net/board/view/43303 , www.acmicpc.net/board/view/59703 를 참조하면 좋겠습니다.

import sys

T = int(input())

for tc in range(T):
    N = int(input())
    result = 0
    arr = [list(map(int,sys.stdin.readline().split())) for _ in range(N)]
    arr.sort()
    min_value = arr[0][1]
    for ind in range(N):
        if ind == 0:
            result += 1
        else:
            if min_value > arr[ind][1]:
                min_value = arr[ind][1]
                result += 1
    print(result)

처음에 입력 받은 그 상태로 서류점수 자체로 sort를 해줬다. 그러면  1번 지원자를 제외한 나머지 지원자들은 이미 서류점수에서, 자기보다 잘 본 사람이 있는 것이다. 

그렇기 때문에 면접점수에서 앞의 사람보다. 순위가 높으면, 두 분야에서 자기보다 잘 본 사람이 있는 것이기 때문에, 최종 탈락하는 것이다.

그래서, 제일 첫번째 지원자의 면접점수를 최소값으로 해주고, 이 값보다 좋은 순위가 있으면 교체를 해주면서 최종합격자 수를 늘려주면 된다.

하지만 이렇게 할시 무조건 처음에 sort를 해야하기 때문에 5000ms 이상의 시간이 걸린다.

import sys

T = int(input())

for tc in range(T):
    N = int(input())
    result = 1
    arr = [0]*(N+1)
    for _ in range(N):
        x,y = map(int,sys.stdin.readline().split())
        arr[x] = y
    min_value = arr[1]
    for ind in range(2,N+1):
        if min_value > arr[ind]:
            min_value = arr[ind]
            result += 1
    print(result)

개선한 방안은 어차피 중복되는 수는 없고 1~N 까지의 순위는 무조건 있기 때문에, 길이가 (N+1)인 1차원 리스트를 만들어주고, index가 서류점수 value가 면접점수가 되도록 한다.

그리고 그 다음은 위와 똑같이 진행해주면 된다.

sort를 진행하지 않기 때문에 실행시간이 확연히 줄어드게 된다.

# 이모티콘 S
# 모두복사
# 클립보드 모두 붙이기
def bfs():
    global S
    stack = [(1,0,0)]

    visited = []
    while stack:
        emo_cnt,clip_cnt,second = stack.pop(0)
        if (emo_cnt,clip_cnt) in visited:
           continue 
        visited.append((emo_cnt,clip_cnt))
        if emo_cnt == S:
            break
        stack.append((emo_cnt,emo_cnt,second+1))
        if emo_cnt and clip_cnt:
            stack.append((emo_cnt+clip_cnt,clip_cnt,second+1))
        if emo_cnt > 2:
            stack.append((emo_cnt-1,clip_cnt,second+1))

    return second


S = int(input())


print(bfs())

기본적으로 bfs를 이용해서 풀었다.

bfs를 이용해서 각 단계마다, 추가가 될 수 있으면 추가를 해주는 방식으로 했다.

하지만 List에서 in을 써서 찾는 방식은 시간복잡도가 커서 오래걸려서 다른 방법으로 한번 더 풀었다.

S = int(input())

Set_emo_clip = set()
Set_emo_clip.add((1,0))
flag = False
time = 0
while True:
    time += 1
    temp_set = set()
    for emo_cnt,clip_cnt in Set_emo_clip:
        if (emo_cnt,emo_cnt) not in Set_emo_clip:
            temp_set.add((emo_cnt,emo_cnt))
        if (emo_cnt+clip_cnt,clip_cnt) not in Set_emo_clip:
            temp_set.add((emo_cnt+clip_cnt,clip_cnt))
            if emo_cnt+clip_cnt == S:
                flag = True
                break
        if emo_cnt > 0 and (emo_cnt-1,clip_cnt) not in Set_emo_clip:
            temp_set.add((emo_cnt-1,clip_cnt))
            if emo_cnt-1 == S:
                flag = True
                break
    if flag:
        break
    Set_emo_clip = Set_emo_clip | temp_set
print(time)

set가 dictionary는 List보다 해당 값이 존재하는지 판별하는데 시간이 더 적게 걸리므로, set과 dictionay형태를 쓰거나,

현재 이모티콘의 개수와 클립보드의 개수를 가지고 방문여부를 판단하니, 적당히 큰 2차원배열를 만들어, 방문여부를 체크하는 것도 한 방식일 것 같다.

set, list not in 비교

import time

list_time = time.time()
a = []

for k in range(100000):
    a.append(k)
    if k not in a:
        pass
print(f'list 추가 및 in 판단 시간 : {time.time()-list_time}')

set_time = time.time()

b = set()

for k in range(100000):
    b.add(k)
    if k not in b:
        pass

print(f'set 추가 및 in 확인 시간 : {time.time()-set_time}')

좀 부정확하겠지만, not in을 판별하는 과정을 추가하는 순간 시간차이가 확 나는걸 알 수 있다.

import collections

N,M = map(int,input().split())
start = int(input())

graph = {i:[] for i in range(N+1)}

for _ in range(M):
    n1,n2,d = map(int,input().split())
    graph[n1].append((n2,d))
visited = [True] * (N+1)
INF = float('inf')
distance = [INF]*(N+1)
distance[start] = 0

node = start

while True:
    visited[node] = False
    for ind,dis in graph[node]:
        distance[ind] = min(distance[ind],distance[node]+dis)
    next_node = -1
    next_min_distance = INF
    for ind in range(N+1):
        if visited[ind] and next_min_distance > distance[ind]:
            next_min_distance = distance[ind]
            next_node = ind
    if next_node != -1:
        node = next_node
    else:
        break

for ind in range(1,N+1):
    if distance[ind] == INF:
        print('INF')
    else:
        print(distance[ind])

평소에 하던 다익스트라 문제였고, 평상시 하던대로 로직을 짜서 실행시켰다 하지만 시간초과라는 결과가 나왔다.

평소에 heapq라는 라이브러리가 익숙치 않아서 쓰지 않았던 heapq를 썼다. heapq를 써서 문제를 풀었다.

import heapq
import sys
N,M = map(int,input().split())
start = int(input())

graph = {i:[] for i in range(N+1)}

for _ in range(M):
    n1,n2,d = map(int,sys.stdin.readline().split())
    graph[n1].append((n2,d))
visited = [True] * (N+1)
INF = float('inf')
distance = [INF]*(N+1)
distance[start] = 0

node_list = []
heapq.heappush(node_list,(0,start))

while node_list:
    current_distance,node= heapq.heappop(node_list)
    visited[node] = True
    if distance[node]<current_distance:
        continue
    for next_node,next_dis in graph[node]:
        if visited[next_node]:
            temp_distance = current_distance + next_dis
            if distance[next_node] > temp_distance:
                distance[next_node] = temp_distance
                heapq.heappush(node_list,(distance[next_node],next_node))

for ind in range(1,N+1):
    if distance[ind] == INF:
        print('INF')
    else:
        print(distance[ind])

heapq를 썼을시에는 통과가 가능했다.

시간복잡도는 heapq가 더 빠르니, heapq에 대해서도 공부해야겠다.

N = int(input())

arr = list(map(int,input().split()))
parent = {i:[] for i in range(N)}
child = {i:[] for i in range(N)}
root_node = -1
for ind in range(N):
    if arr[ind] == -1:
        root_node = ind
    else:
        parent[ind].append(arr[ind])
        child[arr[ind]].append(ind)
remove_node = int(input())
if root_node != remove_node:
    remove_nodes = set()
    stack = [remove_node]
    visited = [True] * N
    while stack:
        node = stack.pop(0)
        remove_nodes.add(node)
        for k in child[node]:
            if visited[k]:
                visited[k] = False
                stack.append(k)
        parent_node = parent[node][0]
        child[parent_node].remove(node)

    leef_nodes = set()

    for ind in range(N):
        if not len(child[ind]):
            leef_nodes.add(ind)
    print(len(leef_nodes-remove_nodes))
else:
    print(0)

가장 자신없고, 공부를 많이 안한 Tree 분야라, 코드가 난잡하다. 기본적인 원리는 parent_node들과 child_node들을 정리해주고, root_node를 구해준다.

만약 지워야할 remove_node와 root_node가 같을시 leafnode가 없으니 0을 출력해준다.

그 외에는 다음과 같이 진행을 한다. 지워진 node들과 leafnode가 될수 있는 node들을 구한뒤 leafnode에서 remove_node를 차집합을 해줘서 그 길이를 출력해준다. 이게 가능했던 이유는 , 반복문을 돌면서 remove_node로 들어간 node들의 child_node를 빼줬기 때문이다.

내가 푼 풀이는 난잡하게 여러 변수들이 존재하고, 깔끔하지 못해서 잘 푸신 다른분의 코드를 클론코딩하면서 공부도 했다.

---- 클론 코딩 및 분석---

# nh7881님 코드 분석

def find_leafs(index,child_nodes):
    # index가 -1이라는 것은 root_node가 remove_node인 경우이니, 그때에는 0을 반환을 해준다.
    if index == -1:
        return 0
    # child_node의 길이가 0인것은 child_Node가 없는 것이므로, leaf_node이다 그러므로 1을 반환해준다.
    if len(child_nodes[index]) == 0:
        return 1
    result = 0
    # 현재 노드인 index의 child_node를 가져와서, 재귀를 실행시켜준다.
    for child_node in child_nodes[index]:
        result += find_leafs(child_node,child_nodes)
    return result



N = int(input())
graph  = list(map(int,input().split()))
# 최상위 노드를 찾아주기 위함이다. 초기값은 node에 존재하지 않는 값으로 해준다.
root_node = -1
remove_node = int(input())
child_nodes = {i:[] for i in range(N)}

for ind in range(N):
    # 우리는 leaf_node를 찾을것이고, 해당 index에 부모 node로 들어온 
    # input값을 반대로 바꿔주는 과정이 필요하다.
    # 만약에 지우는 node와 index가 같으면 굳이 parent을 찾아 child를 넣어주는 과정이 필요없다.
    # 그래서 continue로 넘어가준다.
    # 또한 유일하게 부모가 없는 root_node는 따로 구분을 해준다. if문의 순서가 remove_node가 먼저 앞으로
    # 오는 이유는 remove_node가 root_node일수 있기 때문이다. 이럴때를 구분해주기 위해, remove_node인지 판별하는게 먼저온다.
    # 그외에는 전부 parent_node를 기준으로 child를 추가해주는 방식으로 해준다.
    if remove_node == ind:
        continue
    if graph[ind] == -1:
        root_node = ind
        continue
    child_nodes[graph[ind]].append(ind)

# root_node를 기점으로 leaf_node를 찾는 재귀함수를 실행시켜준다.
print(find_leafs(root_node,child_nodes))

# # # 9019 DSLR 
# # # 레지스터 0이상 10000미만 십진수 저장
# # # n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4
# # # D는 n을 두배로 바꾼다. 결과값이 9999보다 큰 경우는 1만으로 나눈 값 (2n mod 10000)
# # # S : n에서 1을 뺀값 n이 0이면 9999로 대신 저장
# # # L : n을 각자리숫를 왼편으로 회전시켜 그 결과를 레지스터에 저장한다.  d2, d3, d4, d1
# # # R : n을 오른쪽으로 회전 
import collections

def DSLR(num):
    D_num = num *2
    if D_num > 9999:
        D_num = D_num%10000
    S_num = num -1
    if not num:
        S_num = 9999
    L_num = (num*10)%10000 + num//1000
    R_num = num//10 + num%10*1000
    return [D_num,S_num,L_num,R_num]



T = int(input())
DSLR_IND = ['D','S','L','R']
for tc in range(T):
    A,B = list(map(int,input().split()))
    deque = collections.deque()
    deque.append((A,''))
    dp = [0]*10000
    dp[A] = 1
    flag = False
    while deque:
        num,result = deque.popleft()
        if num == B:
            break
        temp = DSLR(num)
        for ind in range(4):
            if not dp[temp[ind]]:
                dp[temp[ind]] = 1
                if temp[ind] == B:
                    result = result + DSLR_IND[ind]
                    flag = True
                    break
                deque.append((temp[ind],result+DSLR_IND[ind]))
        if flag:
            break
    print(result)

이 문제에서 어려웠던 점은 2가지였다.

첫번째는 시간초과의 압박이다. 스트링과 list의 특성을 이용해 L,R을 쉽게 구현을 할려고 했는데, str과 list를 이용해 L,R을 구현하는 순간 시간초과가 계속됬다.

두번째는 L,R의 제대로 된 이해였다.

문제를 처음봤을때 12가 있으면 이게 L이면 21이 되고 R이면 21이 되는줄 알았다. 이렇게 구현을 해놨었는데, 계속 틀렸습니다가 나와서 문제를 찬찬히 읽어보니 이 문제에서는 무조건 4자리로 강제가 되던것이다.

12가 그냥 12가 아닌 0012인 상태인것이다. 그래서 L을 하면 0120이 되는것이고 R을 하면 2001인 것이다. 이부분을 조심해줘서 풀면 되는 것이었다.

이 문제는 modular를 이용해 L,R을 구현해주면 된다.

L은 원래 Number에서 10배를 해주고 10000으로 나머지를 구한뒤, 제일 첫번째 숫자의 몫을 구하기 위해 Number의 1000으로 나눈 몫을 더해주면 된다.

R은 원래 Number를 10으로 나눈 몫을 구하고, 나머지에는 1000을 곱해서 더해주면 된다.

그리고 bfs를 이용해서 풀때, 목표값인 B와 비교를 해주는 것을 for문 밖 popleft를 한 바로 뒤에 나뒀더니, 의미없는 반복문이 더 진행이 되었기 때문에, for문 안에 두어서 바로바로 비교한뒤 flag를 두어서, 바로 결과가 출력되게 만들어줬다.

def check():
    global N,H
    for ind in range(N):
        current_ind = ind
        for k in range(H):
            if visited[k][current_ind]:
                current_ind += 1
            elif current_ind>0 and visited[k][current_ind-1]:
                current_ind -= 1
        if current_ind != ind:
            return False
            
    return True




def dfs(row_index,col_index,cnt,limit):
    global N,H,result
    if cnt > limit:
        return
    if check():
        result = min(cnt,result)
        return
    for k in range(row_index,H):
        if k == row_index:
            search_y = col_index
        else:
            search_y = 0
        for y in range(search_y,N-1):
            if not visited[k][y] and not visited[k][y+1]:
                visited[k][y] = 1
                dfs(k,y+2,cnt+1,limit)
                visited[k][y] = 0









N,M,H = map(int,input().split())
# H는 놓을 수 있는 개수
# M 은 가로선의 개수
# 앞은 가로선의 위치 뒤는 2개의 위치
result = float('inf')
visited = [[0]*N for _ in range(H)]
for _ in range(M):
    row,node = map(int,input().split())
    visited[row-1][node-1] = 1
if check():
    print(0)
else:
    for limit_insert_rows in range(1,4):
        dfs(0,0,0,limit_insert_rows)
        if result != float('inf'):
            print(result)
            break
    else:
        print(-1)

문제에서 최고로 놓을  수 있는 사다리의 개수는 3개가 최대이므로, 기본적으로 전체 사다리를 놓을 수 있는 위치를 골라서 재귀로 푸는 방식으로 해줬다. 그리고 result값이 바뀌면 break로 탈출을 해줬다. 

사다리의 가로선의 정보를 node-1,node 둘 중 왼쪽인 node-1에 저장해줬다.

그리고 사다리가 놓을 수 없는 조건은 현재 위치인 [가로선][세로선] 과 [가로선][세로선+1] 위치에 전부 0이 존재하면 사다리를 놓을 수 있다고 가정했다. 그리고 난뒤 재귀함수에서 y축을 +2만큼 이동시켜줬다. 그 이유는 해당 가로선에서  내가 고른 세로선에서 사다리를 놓게 되면 세로선 과 세로선+1의 위치에는 사다리를 놓을 수 없다. 그러므로, y를 +2 해주었다.

그리고, 가로선 중에서 주어진 row_index가 같을때에만 그러고 그 다음 가로선부터는 전체 세로선에 대해서 탐색하면 된다.

이렇게 사다리를 추가해주면서, check()라는 함수를 통해, 문제에 주여진 조건인 start_index와 사다리를 통과하고 나온 index가 같은지 비교를 해줘서 True,False 값을 반환시켜주었다.

이렇게 풀었지만, 다른 사람들의 코드를 공부하고 더 나은 풀이로 나중에 고쳤다.

import sys
def check():
    global N,H
    for ind in range(N):
        current_ind = ind
        for k in range(H):
            current_ind += visited[k][current_ind]
        if current_ind != ind:
            return False
            
    return True




def dfs(ladder_index,cnt,limit):
    global N,H,result
    if limit == cnt:
        if check():
            result = limit
        return
    for ind in range(ladder_index,N*H):
        row_index = ind//N
        col_index = ind%N
        if col_index == N-1:
            continue
        if not visited[row_index][col_index] and not visited[row_index][col_index+1]:
            visited[row_index][col_index] = 1
            visited[row_index][col_index+1] = -1
            dfs(ind+2,cnt+1,limit)
            if result != 4:
                return
            visited[row_index][col_index] = 0
            visited[row_index][col_index+1] = 0





N,M,H = map(int,input().split())
# H는 놓을 수 있는 개수
# M 은 가로선의 개수
# 앞은 가로선의 위치 뒤는 2개의 위치
if M == 0:
    print(0)
else:
    result = 4
    call = 0
    visited = [[0]*N for _ in range(H)]
    for _ in range(M):
        row,node = map(int,sys.stdin.readline().split())
        visited[row-1][node-1] = 1
        visited[row-1][node] = -1

    if check():
        print(0)
    else:
        for k in range(1,4):
            dfs(0,0,k)
            if result != 4:
                break
        if result != 4:
            print(result)
        else:
            print(-1)

 기본적인 원리는 비슷하다. 하지만 몇몇 부분에서 백트래킹을 해줬다.

먼저 좌측에만 가로선의 정보를 저장했던 거에서, 좌우측에 정보를 저장해줬다. 대신 그 값을 1과 -1을 저장시켜줬다.

이전 코드에서 좌측에 있는지 우측에 있는지 판별해서 세로선의 index를 바꿔주던거에서 좀 더 깔끔하게 바꿔주었다.

그리고 매 함수마다 check를 해주던 것을 cnt == limit에 도달했을때, check를 해주었다.

또한 결과값의 기본값이 바뀌었을때 break를 해주는 곳을 여러군데 추가해줬다.

가장 크게 바뀐 것은 2중 for문을 돌리던 것을 단일 for문으로 바꿔주었다.

다음과 같이 세로선 8과 가로선 4일때를 그려보면 다음과 같이 사다리를 그릴수 있을 것이다.

여기서 각각의 교차선을 구한다고 생각하면,

다음과 같이 세로선 8* 가로선 4 만큼의 교차선이 나올 수 있다. 그러므로 문제에 주어진 N*H 만큼의 교차선이 주어질 수 있다.

이 중에서 사다리를 놓을 수 있는 교차선은 빨간색 동그라미가 쳐진 교차선 뿐이다. N번 세로선인 8번 세로선에는 그 다음 세로선이 없기 때문에 사다리를 놓을 수 없다.

그 외의 나머지 부분 교차선에 사다리를 놓는다고 생각하고 재귀함수를 돌리면 된다. 위에서 설명 했듯이 한 곳에 사다리를 놓을시, 해당 교차선 위치에서 가로로 2칸만큼 더 가야지만 사다리를 놓을 수 있다. 

    for ind in range(ladder_index,N*H):
        row_index = ind//N
        col_index = ind%N
        if col_index == N-1:
            continue
        if not visited[row_index][col_index] and not visited[row_index][col_index+1]:
            visited[row_index][col_index] = 1
            visited[row_index][col_index+1] = -1
            dfs(ind+2,cnt+1,limit)
            if result != 4:
                return
            visited[row_index][col_index] = 0
            visited[row_index][col_index+1] = 0

함수에서 이부분이 교차선을 나타내고, 교차선의 가로선과 세로선을 찾아내서 세로선이 마지막 위치한 것이면 넘어가고, 

사다리를 놓을 수 있으면, 사다리를 놓은 뒤, 해당 index에서 +2를 해줘서 재귀함수를 해준다.

구현은 안했지만, 가능한 또 다른 방법은 사다리를 놓을 수 있는 교차선들을 전부 구해놓은 상태에서, 조합을 이용해 사다리를 1개 놓았을 때, 2개 놓았을 때, 3개 놓았을 때,를 구분하고, 고른 사다리가 문제가 없는지 판별해주고, 문제에 조여진 조건대로 시작 index와 도착 index를 같은지 판별하는 방법을 써도 될것 같다.

문제 자체는 어렵게 보이지 않았지만, 실제로 구현하는데에 어려운점이 많았고, 많이 틀렸던 문제였다.

중간중간 가능성이 없는것을 멈춰주고, 시간을 줄이는데 노력해야지 풀 수 있었던 힘들었던 문제였다.

# 18231 파괴된 도시






N,M = map(int,input().split())

graph = {i:[] for i in range(N+1)}

for _ in range(M):
    node1,node2 = map(int,input().split())
    graph[node1].append(node2)
    graph[node2].append(node1)

destory_cnt = int(input())
destroy_citys = list(map(int,input().split()))
result = []
destroyed = []
for destroy_city in destroy_citys:
    temp = [destroy_city]
    for city in graph[destroy_city]:
        if city not in destroy_citys:
            break
        else:
            temp.append(city)
    else:
        result.append(destroy_city)
        destroyed.extend(temp)
    if len(set(destroyed)) == destory_cnt:
        print(len(result))
        result.sort()
        print(' '.join(list(map(str,result))))
        break
else:
    print(-1)

이 문제는 여러가지 경우의 답이 나올수 있으나, 정답이 되는 1개만 출력하면 된다.

기본 원리는 이렇다. 그래프라는 딕셔너리에 양방향으로 노드를 전부 저장해놓는다.

그리고 파괴된 도시 목록을 입력을 받아, for문을 돌리는데, 만약 파괴된 도시 중 하나의 인접 노드들 중에 파괴된 노드들이 하나도 없으면 for문을 중지하고, 나온다. 그렇지 않을경우는 해당 도시는 파괴가 시작된 도시로 볼 수 있으므로, 결과목록에 넣어준다.

또한 해당 도시로 폭파된 도시 목록도 별도의 리스트에 저장해준다.

이렇게 반복을 해주면서, 별도로 저장해놓은 폭파된 도시목록을 set을 해줬을때의 길이가, 전체 파괴된 도시수와 동일하다면 for문을 중지하고, 결과를 보여준다.

위의 해당사항이 하나도 없을 시에는 -1을 출력해주면 된다.