# 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를 쓰도록 하자. 안 그러면 시간 초과가 난다.
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 늘려주면 된다.
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를 같은지 판별하는 방법을 써도 될것 같다.
문제 자체는 어렵게 보이지 않았지만, 실제로 구현하는데에 어려운점이 많았고, 많이 틀렸던 문제였다.
중간중간 가능성이 없는것을 멈춰주고, 시간을 줄이는데 노력해야지 풀 수 있었던 힘들었던 문제였다.
# 1038 감소하는 수
# X의 자릿수가 가장 큰 자릿수
import collections
def dfs(N):
deque = collections.deque()
for i in range(1,10):
deque.append((i,str(i)))
while deque:
if len(result) == N+1:
break
cur_num,to_num = deque.popleft()
if cur_num != 0:
for k in range(cur_num):
temp = to_num + str(k)
deque.append((k,temp))
result.append((temp))
N = 1023
result = []
for i in range(10):
result.append(i)
if N >=10:
dfs(N)
if len(result) > N:
print(result[N])
else:
print(-1)
기본적인 백트래킹 문제이다. 처음에 1~9의 수를 넣어주고, 그보다 낮은 자리수에서 더 낮은 값을 넣어주면서 결과값에 넣어주고, 해당 길이를 초과하는 N이 나올시에는, -1을 출력하도록 했따.
