Coding 공부

# 1987 알파벳

def dfs(x,y,visited,cnt):
    global result,const,ccs
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx< R and 0<= ny<C and visited[ord(arr[nx][ny])-const]:
            visited[ord(arr[nx][ny])-const] = False
            dfs(nx,ny,visited,cnt+1)
            visited[ord(arr[nx][ny])-const] = True
    if cnt > result:
        result = cnt
ccs = 0
R,C = map(int,input().split())
dx = [-1,1,0,0]
dy = [0,0,-1,1]
arr = [list(input()) for _ in range(R)]
result = 1
visit = [True]*26
const = ord('A')
visit[ord(arr[0][0])-const] = False
dfs(0,0,visit,1)

print(result)

시간 초과의 늪에 빠졌던 문제이다. 기본적인 원리는 찾았으나, 문제를 해결하기 위한 방안을 찾기위해 노력했던 문제이다.

처음으로 풀었던 방식은 원래는 visited를 하나의 집합으로 해서 있는지 없는지 체크를 했다면, 알파벳에 해당되는 visited 리스트를 만들어주고 check 해주는 방식으로 풀었다.

# 1987 알파벳


R,C = map(int,input().split())

arr = [list(input()) for _ in range(R)]
check = [['']*C for _ in range(R)]

stack = [(0,0,1,arr[0][0])]
result = 0
dx = [-1,1,0,0]
dy = [0,0,1,-1]
while stack:
    x,y,cnt,total = stack.pop()
    if result < cnt:
        result = cnt
    if result == 26:
        break
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < R and 0<= ny <C:
            if arr[nx][ny] not in total:
                temp = total + arr[nx][ny]
                if check[nx][ny] != temp:
                    check[nx][ny] = temp
                    stack.append((nx,ny,cnt+1,temp))
print(result)

시간이 빠른 방식은 다음과 같다. visited를 체크하는 것은 하나의 스트링을 통해 그 안에 있는지 없는지 확인하는 것이다.

여기까지는 동일하다. 하지만 결정적으로 다른것은 check라는 행렬을 통해 또 체크 하는 것이다.

지금까지 온 이동경로를 넣어놓는 check라는 행렬이다. 이 행렬에 존재하는 값과 같으면, 이미 그에 대해서 전부 탐색을 한 것이기 때문에 또 다시 탐색할 필요가 없다.

탐색한 경로들을 캐싱해놓은것과 같다. 서로다른 루트로 왔다 하더라도 다음위치에 똑같은 값으로 들어오는 거면 굳이 한번 더 검색을 할 필요가 없다.

이 방법은 dfs나 bfs 상관은 없으나 bfs를 할 시, collections의 deque를 쓰도록 하자. 안 그러면 시간 초과가 난다.

import heapq
import sys
N = int(input())


max_heapq = []
min_heapq = []
for _ in range(N):
    number = int(sys.stdin.readline())
    if len(max_heapq) == len(min_heapq):
        heapq.heappush(max_heapq,-number)
    else:
        heapq.heappush(min_heapq,number)
    if min_heapq and max_heapq and min_heapq[0] < -max_heapq[0]:
        max_number = -heapq.heappop(max_heapq)
        min_number = heapq.heappop(min_heapq)

        heapq.heappush(max_heapq,-min_number)
        heapq.heappush(min_heapq,max_number)
    print(-max_heapq[0])

우선순위 힙을 사용하는 기본적인 문제인 것 같다.

과거에도 다익스트라 알고리즘 문제를 풀때 우선순위힙큐를 사용했지만, 여전히 우선순위 힙을 사용하는데, 어려움을 겪었던 문제다.

문제 자체의 기본적인 생각은 다음과 같다. 

가운데 값을 기준으로 가운데 값보다 큰 경우는 무조건 우측에 두는 것이다.  그리고 작은 값은 좌측에 두는 것이다.

그러므로, min_heapq는 가운데 값을 기준으로 우측에 있는 값이고, max_heapq는 가운데 값을 기준으로 좌측에 있는 값이다.

문제 조건 중 가운데 값을 출력하고, 짝수일경우 가운데 값 2개 중 작은 값을 출력을 해야한다. 그러므로, max_heapq가 min_heapq보다 크기가 커야한다. 그래서 max_heapq와 min_heapq가 같은 크기이면, max_heapq에 먼저 넣어주고, 아닐 경우 min_heapq를 넣어줘야한다.

그리고 heapq는 무조건 최소값을 pop해주는 특징이 있으므로, max_heapq를 저장할때에는 가장 큰 값이 가장 먼저 나올수 있도록 -를 곱해줘야한다.

순서에 따라 맞춰서 max_heapq와 min_heapq에 순차적으로 넣어줘야한다. 하지만, 들어오는 입력값에 따라 가끔씩 min_heapq의 첫번째값이 max_heapq의 첫번째값보다 작은 경우가 생길수가 있다. 그럴 경우 두개를 바꿔주는 과정이 필요하다.

무조건 max_heapq의 첫번째 값이 전체의 가운데값이 되기위한 조치이다.

그리고 난뒤에, max_heapq의 첫번째 값을 출력해주면 된다.

heapq라는 라이브러리를 사용하면, 그리 어렵지 않은 문제이다. 하지만 나는 아직 트리와 우선순위힙에 대해서 잘 모르므로, 나중에 트리와 우선순위힙에 대해 더 자세히 공부하고, 라이브러리가 아닌 직접 구현으로 풀 수 있도록 연습해야겠다. 

# 3197번 Fail

import sys
def find(number):
    if parents[number] == number:
        return number
    parents[number] = find(parents[number])
    return parents[number]

def merge(root,child):
    parents[child] = root

def water_merge():
    while water:
        cx,cy = water.pop(0)
        flag = True
        for k in range(4):
            nx = cx + dx[k]
            ny = cy + dy[k]
            if 0<= nx <R and 0<= ny <C:
                if check_map[nx][ny] != -1 and check_map[nx][ny] != check_map[cx][cy]:
                    parentA = find(check_map[cx][cy])
                    parentB = find(check_map[nx][ny])
                    if parentA != parentB:
                        merge(parentA,parentB)
                        check_map[nx][ny] = parentA
                elif check_map[nx][ny] == -1 and flag:
                    melt_water.append((cx,cy))
                    flag = False


def water_melt():
    while melt_water:
        cx,cy = melt_water.pop(0)
        root = find(check_map[cx][cy])
        for k in range(4):
            nx = cx + dx[k]
            ny = cy + dy[k]
            if 0<= nx <R and 0<= ny <C:
                if check_map[nx][ny] == -1:
                    water.append((nx,ny))
                    check_map[nx][ny] = root        

R,C = map(int,input().split())

arr = [list(sys.stdin.readline()) for _ in range(R)]
check_map = [[-1]*C for _ in range(R)]
parents = [-1]*(R*C)
cnt = 0
dx = [-1,1,0,0]
dy = [0,0,-1,1]
swan = []
water = []
for x in range(R):
    for y in range(C):
        if arr[x][y] == '.' or arr[x][y] == 'L':
            water.append((x,y))
            parents[cnt] = cnt
            check_map[x][y] = cnt
            cnt += 1
            if arr[x][y] == 'L':
                swan.append((x,y))

swan1 = swan[0]
swan2 = swan[1]
time = 0
melt_water = []
while water:
    water_merge()
    if find(check_map[swan1[0]][swan1[1]]) == find(check_map[swan2[0]][swan2[1]]):
        result = time
        break
    water_melt()
    time += 1

            
print(result)

처음 시도했던 실패버전이다.

이 방법은 물을 union find로 한 묶음으로 한뒤, 탐색을 해주는 방식으로 했다. 그러나 이 방식의 문제점은 각 time에 대해 전부다 백조가 연결되어있는지 확인해야 하므로, 시간이 초과가 되었다. 

import sys
from collections import deque
import time
def isconnent_swan(start,end,standard_time):
    global R,C
    visited = [[True] * C for _ in range(R)]
    stack = deque()
    stack.append((start[0],start[1]))
    visited[start[0]][start[1]] = False
    while stack:
        x,y = stack.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<= nx <R and 0<= ny <C:
                if melt_time[nx][ny] <= standard_time and visited[nx][ny]:
                    visited[nx][ny] = False
                    stack.append((nx,ny))
                    if nx == end[0] and ny == end[1]:
                        return True

    return False


def find_max_spend_time():
    global R,C
    while waters:
        x,y,time = waters.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<= nx < R and 0<= ny < C:
                if melt_time[nx][ny] == -1:
                    melt_time[nx][ny] = time + 1
                    waters.append((nx,ny,time+1))
    return time
R,C = map(int,input().split())
origins = [list(sys.stdin.readline()) for _ in range(R)]
melt_time = [[-1]*C for _ in range(R)]
waters = deque()
swans = []
dx = [-1,1,0,0]
dy = [0,0,-1,1]
for x in range(R):
    for y in range(C):
        if origins[x][y] != 'X':
            waters.append((x,y,0))
            melt_time[x][y] = 0
            if origins[x][y] == 'L':
                swans.append((x,y))


max_time = find_max_spend_time()
min_time = 0
result = 0
while min_time <= max_time:
    mid_time = (min_time + max_time)//2
    if isconnent_swan(swans[0],swans[1],mid_time):
        answer = mid_time
        max_time = mid_time - 1
    else:
        min_time = mid_time + 1

print(answer)

두번째로 찾은 방법은 빙하가 녹는 시간을 미리 구해주는 것이다. BFS를 통해 각 빙하들이 녹는 시간들을 찾아주고, 이분탐색으로 시간을 줄여가면서 백조들끼리 연결되어있는지 구하는 것이다.

빙하가 녹는시간을 구해놓고, 기준시간보다 작거나 같을시에는 이동이 가능하다고 판별을 해주었다.

하지만 이 방법도 백조가 연결되어있는지 매번 BFS를 해야하므로, 실행시간이 오래걸리는 편이었다.

from collections import deque
import sys
R,C = map(int,input().split())

lake = [list(sys.stdin.readline()) for _ in range(R)]
waters = deque()
swans = []
water_chk = [[True] *C for _ in range(R)]
swan_chk = [[True] *C for _ in range(R)]
for x in range(R):
    for y in range(C):
        if lake[x][y] != 'X':
            waters.append((x,y))
            water_chk[x][y] = False
            if lake[x][y] == 'L':
                swans.append((x,y))
                lake[x][y] = '.'
start_swan,end_swan = swans
swans = deque()
swans.append(start_swan)
swan_chk[start_swan[0]][start_swan[1]] = False
times = 0
new_water = deque()
new_swans = deque()
dx = [-1,1,0,0]
dy = [0,0,-1,1]
while True:
    while waters:
        x,y = waters.popleft()
        lake[x][y] = '.'
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<= nx < R and 0<= ny <C:
                if lake[nx][ny] == 'X' and water_chk[nx][ny]:
                    new_water.append((nx,ny))
                    water_chk[nx][ny] = False
    while swans:
        x,y = swans.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx <R and 0<=ny<C:
                if swan_chk[nx][ny]:
                    if lake[nx][ny] == '.':
                        swans.append((nx,ny))
                    elif lake[nx][ny] == 'X':
                        new_swans.append((nx,ny))
                    swan_chk[nx][ny] = False

    if not swan_chk[end_swan[0]][end_swan[1]]:
        answer = times
        break
    waters = new_water
    swans = new_swans
    new_swans = deque()
    new_water = deque()
    times += 1

print(answer)

마지막 방식은 deque를 4개를 써서, 매번 bfs를 처음부터 하지 않아도, 되는 방식으로 해주었다.

water : 현재가 물인 상태인 것들이 모아져있는 deque

new_water : 다음 시간에 녹아질 예정인 빙하들의 deque

swan : 현재 시간에 swan이 돌아다닐수 있는 deque

new_swan : 다음 시간에 swan이 움직일수 있는 deque

이렇게 기능적으로 나눈뒤에,

먼저 water에서 다음에 녹을 water를 찾아준다. 이때 new_water에 들어가는 것은 호수에 빙하인것과 water_chk 한번도 방문하지 않은 곳이여야 한다.

그리고 여기서 처음 water를 pop할때 lake[x][y]를 . 를 입력해주는 것은 이전 time에 우리가 찾아놓은 new_water가 녹았기 때문에, 이때 값을 변경시켜주는 것이다.

이렇게 한뒤에, swan를 bfs를 돌리면서 물인곳은 계속 swan에 추가해서 bfs를 해주고, 만약 빙하인곳은 다음번에 들릴곳이기 때문에 new_swan에 넣어준다.

그리고 빙하와 물 상관없이 swan 방문을 check해준다.

이렇게 작업을 한뒤에, 우리가 찾는 반대편 swan에 도착했는지 확인을 해주고, 그때의 시간을 출력해주면 된다.

도착하지 않았으면, new_water를 water에 넣어주고, new_swan을 swan에 넣어준뒤 초기화를 시켜준다

# 1309 동물원
# 9901로 나눈 수 출력

N = int(input())
mod = 9901
dp = [0]*(N+1)
if N == 1:
    print(3)
else:
    dp = [1,3]
    for i in range(2,N+1):
        current = 2*dp[-1]+dp[-2]
        dp[-2] = dp[-1]
        dp[-1] = current
    print(current%mod)

직접 그려봐서 점화식을 찾았다.

생각해보면 N-1일때, N-1의 위치에 왼쪽에 사자가 있을때, 오른쪽에 사자가 있을때와 둘다 없을때가 있을 것이다.

파란색 음영이 있는 곳이 사자가 있다고 한다고 가정하면, N-1 번 위치에 사자가 있을때에는 2가지의 경우의 수가 있다. 그리고 N-1에 사자가 없을때에는 총 3가지가 있다. 그 중에서 둘다 사자가 없는 경우는 N-2의 크기에서 사자를 놔두는 경우의 수가 같은 것이다.

점화식을 구하면,

F(N) = F(N-1)*2 +F(N-1) 로 나타낼 수 있다.

이렇게 구하고, 전체를 구해서 9901로 나눠도 되지만, 그냥 하면, 숫자가 워낙 커지므로 9901로 나눈 나머지로 계산하는 것이 더 빨리 결과가 나온다.

N = int(input())

prev = 1
result = 3
mod = 9901
for _ in range(N-1):
    temp = result
    result = (result*2 + prev)%mod
    prev = temp
print(result)

# 11403 경로 찾기



N = int(input())
arr = [list(map(int,input().split())) for _ in range(N)]
for k in range(N):
    for x in range(N):
        for y in range(N):
            if arr[x][k] + arr[k][y] == 2:
                arr[x][y] = 1

for i in range(N):
    print(*arr[i])

풀고보니 플로이드 와샬 문제였다.

중간 경로를 통해서 두개가 연결이 되는 경우 arr를 갱신해주는 방식으로 했다.

이 방식 말고도 BFS,DFS를 통해 node들을 탐색해서 푸는 방식도 있다.

# 9251 LCS
def LCS(SA,SB,SALEN,SBLEN):
    global LCS_list

    for i in range(1,SALEN+1):
        for j in range(1,SBLEN+1):
            if SA[i-1] == SB[j-1]:
                LCS_list[i][j] = LCS_list[i-1][j-1]+1
            else:
                LCS_list[i][j] = max(LCS_list[i-1][j],LCS_list[i][j-1])




A = list(input())
B = list(input())

lenA = len(A)
lenB = len(B)

LCS_list = [[0]*(lenB+1) for _ in range(lenA+1)]

LCS(A,B,lenA,lenB)

print(LCS_list[lenA][lenB])

이전에 풀었던 LCS의 이전버전이다.

푸는 방식은 동일하고 여기서는 길이만 구해주는거라 길이만 구해줬다.

# 14499 주사위 굴리기
# N*M 지도
# 주사위는 윗면이 1 동쪽방향이 3인 상태로 놓아진다.
def roll(direction,nx,ny):
    global dice,map_list
    if direction == 1:
        dice[0],dice[2],dice[3],dice[5] = dice[3],dice[0],dice[5],dice[2]
    elif direction == 2:
        dice[0],dice[2],dice[3],dice[5] = dice[2],dice[5],dice[0],dice[3]
    elif direction == 3:
        dice[0],dice[1],dice[4],dice[5] = dice[4],dice[0],dice[5],dice[1]
    else:
        dice[0],dice[1],dice[4],dice[5] = dice[1],dice[5],dice[0],dice[4]
    if map_list[nx][ny]:
        dice[5] = map_list[nx][ny]
        map_list[nx][ny] = 0
    else:
        map_list[nx][ny] = dice[5]


N,M,X,Y,K = map(int,input().split())

map_list = [list(map(int,input().split())) for _ in range(N)]

# [1,2,3,4,5,6] 
# 동쪽 1 [4,2,1,6,5,3]
# 서쪽 2 [3,2,6,1,5,4]
# 북쪽 3 [5,1,3,4,6,2]
# 남쪽 4 [2,6,3,4,1,5]
dice = [0]*6
dire = [(0,1),(0,-1),(-1,0),(1,0)]

command_list = list(map(int,input().split()))
for command in command_list:
    nx = X + dire[command-1][0]
    ny = Y + dire[command-1][1]
    if 0<=nx<N and 0<=ny<M:
        roll(command,nx,ny)
    else:
        continue
    X,Y = nx,ny
    print(dice[0])

첫 풀이방식은 문제에 주어진 조건을 그대로 따라 했다.

문제에서 보여준 전개도 대로 실행했다. 일단 크기가 6인 리스트를 만들어 주사위로 지정을 했다.

문제에서 보여준 전개도에서 각 위치에 해당하는 값은 전개도에 있는 값의 -1에 인덱스에 저장을 했다.

즉 정 가운데는 0번 인덱스, 3번 위치에 있는것은 2번 인덱스에 저장을 했다. 

이런식으로 주사위를 가정하고, 주사위를 동서남북으로 돌렸을때, 인덱스가 바뀌는 위치를 계산해줬다. 그리고 동서남북에 따라, 주사위가 바뀌는 것을 구현해주었다.

동서남북명령어가 1,2,3,4로 들어오니 그에 맞춰  이동값을 dire에 저장해줬다. 그 다음에는 명령어를 실행시켜주는 반복문을 하고, 범위를 벗어나는 경우에는 아무것도 출력을 하면 안되니 범위를 벗어나는 경우에는 continue로 넘어가준다. 그렇지 않을 때에는, roll이라는 함수를 실행시켜 주사위를 굴리고, 그 위치에 존재하는 값에 따라 문제에 주여진 조건대로 실행시켰다.

하지만 이렇게 풀고난뒤 한가지 불만점이 있었는데, 각 케이스마다 전부 하나하나 인덱스를 바꿔주는 로직이 마음에 들지 않았다.

그래서 개선한 코드는 다음과 같다.

# 14499 주사위 굴리기
# N*M 지도
# 주사위는 윗면이 1 동쪽방향이 3인 상태로 놓아진다.
def roll(direction,nx,ny):
    global dice,map_list,moving_dice
    dice[0],dice[-1],dice[moving_dice[direction][0]],dice[moving_dice[direction][1]] = dice[moving_dice[direction][0]],dice[moving_dice[direction][1]],dice[-1],dice[0]
    if map_list[nx][ny]:
        dice[5] = map_list[nx][ny]
        map_list[nx][ny] = 0
    else:
        map_list[nx][ny] = dice[5]


N,M,X,Y,K = map(int,input().split())

map_list = [list(map(int,input().split())) for _ in range(N)]

# [1,2,3,4,5,6] 
# 동쪽 1 [4,2,1,6,5,3]
# Top,Bottom,바뀔것1,바뀔것2 = 바뀔것1,바꿀것2,bottm,top
# 서쪽 2 [3,2,6,1,5,4]
# 북쪽 3 [5,1,3,4,6,2]
# 남쪽 4 [2,6,3,4,1,5]
dice = [0]*6
dire = [(0,1),(0,-1),(-1,0),(1,0)]
moving_dice = {1 : [3,2],2:[2,3],3:[4,1],4:[1,4]}
command_list = list(map(int,input().split()))
for command in command_list:
    nx = X + dire[command-1][0]
    ny = Y + dire[command-1][1]
    if 0<=nx<N and 0<=ny<M:
        roll(command,nx,ny)
    else:
        continue
    X,Y = nx,ny
    print(dice[0])

나머지 로직은 전부 동일하지만, 주사위가 굴러갈때의 규칙성이 있다.

규칙은 다음과 같다.

주사위는 총 6면이 있고, 서로 마주보는걸로 묶을시 3쌍으로 볼수 있다. 주사위를 굴릴 시, 우리가 굴리기전의 Top,bottom 한 쌍과 주사위를 굴러오서 오는 한쌍이 위치가 바뀌고 나머지 한쌍은 그대로 위치한다.

           Prev                               -- >>                        Next

굴렸을때 Top에 가는 거                                                 Top

굴렸을때 Bottom에 가는 거                                           Bottom

            Top                                              Prev에서 굴렸을때 Bottom에 가는것이 있었던 위치

         Bottom                                            Prev에서 굴렸을때 Top에 가는 것이 있었던 위치

글로 설명하기 좀 힘든데 이러한 특징점을 가지고 있따. 그러므로 각 명령어마다, 바뀌는 Index값을 Dictionary에 저장해놓고, 위의 걸 구현해주었다.

같은 코드를 여러번 반복하는 것을 막을 수 있었다. 당연히 실전에서는 위의 풀이방식대로 풀 것 같다.

def nqueen(x):
    global cnt
    for i in range(x+1):
        if x != i:
            if (visited[i] == visited[x]) or (abs(visited[i]-visited[x]) == abs(i-x)):
                return
    if x == N-1:
        cnt += 1
        return
    for i in range(N):
        visited[x+1] = i
        nqueen(x+1)



N = int(input())
cnt = 0
visited = [-1] * N
for i in range(N):
    visited[0] = i
    nqueen(0)
print(cnt)

백트래킹을 이용한 유명한 문제 중 하나이다.

적절하게 백트래킹을 하지 않고, 전체탐색을 할시 순열이라, 시간초과가 날 수 밖에 없다.

이 문제는 N과 같은 크기의 visited 1차원 리스트를 만들어줬다.

각 인덱스는 행을 나타내고, 그 안의 값은 열을 나타낸다고 가정을 하자.

그래서 첫번째 행에 0~N-1까지 넣어주고 그 뒤에 nqueen이라는 함수를 실행시켰다.

이 안에서도, 각 인덱스를 넣어주면서 재귀를 진행하는데, 만약에 값이 같은게 있거나, 인덱스의 차와 값의 차이가 동일하시 이것은 대각성분에 존재하는것이므로 종료를 해준다.

위 조건에 걸리지 않고 N-1까지 오면, 모든 곳을 탐색한 것이므로 함수를 종료해주면서 cnt를 1 늘려주면 된다.