글 읽기 - 1520 테스트 케이스 요청

greentec 9년 전 0

예제 입력은 맞는데 제출하면 틀리네요...

처음 한 개만 받을 수 있을지 질문드려봅니다.

baekjoon 9년 전 0

테스트 케이스는 제공하지 않습니다.

죄송합니다.

질문 글을 올리시면, 어떤 부분에서 틀렸는지 알려드릴 수 있습니다.

greentec 9년 전 0

네;; 아래와 같습니다.

def dfs(i,j,score):
    global count
    global edges
    global stack

    
    if i==n[0] and j==n[1]:
        count += 1
        return 0
    if marked[i][j] == False:
        marked[i][j]=True

        if marked[i-1][j] == False and m[i-1][j]<score:
            temp=','.join([str(s) for s in [i,j,i-1,j]])
            if temp in edges:
                stack.append(temp)
                del edges[temp]
                dfs(i-1,j,m[i-1][j])
        if marked[i+1][j] == False and m[i+1][j]<score:
            temp=','.join([str(s) for s in [i,j,i+1,j]])
            if temp in edges:
                stack.append(temp)
                del edges[temp]
                dfs(i+1,j,m[i+1][j])
        if marked[i][j-1] == False and m[i][j-1]<score:
            temp=','.join([str(s) for s in [i,j,i,j-1]])
            if temp in edges:
                stack.append(temp)
                del edges[temp]
                dfs(i,j-1,m[i][j-1])
        if marked[i][j+1] == False and m[i][j+1]<score:
            temp=','.join([str(s) for s in [i,j,i,j+1]])
            if temp in edges:
                stack.append(temp)
                del edges[temp]
                dfs(i,j+1,m[i][j+1])

    if len(edges) != 0:
        temp=stack.pop()
        if temp not in edges:
            edges[temp] = 1
        marked[i][j] = False
    else:
        return 0
    

n=map(int, raw_input().split())
m=list()
marked=list()

m.append([10001]*(n[1]+2))
marked.append([False]*(n[1]+2))

for i in range(1,n[0]+1):
    m.append(list())
    m[i].append(10001)
    m[i].extend(map(int,raw_input().split()))
    m[i].append(10001)
    marked.append([False]*(n[1]+2))
    
m.append([10001]*(n[1]+2))
marked.append([False]*(n[1]+2))

edges=dict()
stack=list()
#find Edges
for i in range(1,n[0]+1):
    for j in range(1,n[1]+1):
        if m[i][j]>m[i-1][j]:
            edges[','.join([str(s) for s in [i,j,i-1,j]])] = 1
        if m[i][j]>m[i+1][j]:
            edges[','.join([str(s) for s in [i,j,i+1,j]])] = 1
        if m[i][j]>m[i][j-1]:
            edges[','.join([str(s) for s in [i,j,i,j-1]])] = 1
        if m[i][j]>m[i][j+1]:
            edges[','.join([str(s) for s in [i,j,i,j+1]])] = 1

count=0
dfs(1,1,m[1][1])

print count

    

baekjoon 9년 전 0

이런 데이터를 넣으면 틀리네요.

greentec 9년 전 0

아, 그렇군요;; 감사합니다!

greentec 9년 전 0

코드를 간결하게 만들어서 위 테스트 케이스는 통과했는데 시간초과가 걸리네요;

백트래킹을 써야 하는 건가요?

def dfs(i,j,score):
    global count
    if i==n[0] and j==n[1]:
        count+=1
        return 0
    
    if m[i-1][j]<score:
        dfs(i-1,j,m[i-1][j])
    if m[i+1][j]<score:
        dfs(i+1,j,m[i+1][j])
    if m[i][j-1]<score:
        dfs(i,j-1,m[i][j-1])
    if m[i][j+1]<score:
        dfs(i,j+1,m[i][j+1])

    return 0
    
n=map(int, raw_input().split())
m=[]
m.append([99999]*(n[1]+2))
for i in range(1, n[0]+1):
    m.append(list())
    m[i].append(99999)
    m[i].extend(map(int, raw_input().split()))
    m[i].append(99999)
m.append([99999]*(n[1]+2))

count=0
dfs(1,1,m[1][1])

print count

h0ngjun7 9년 전 0

입력으로 들어오는 수들 중, 작은 수부터 보면서 동적계획법을 사용해주시면 됩니다. 시간복잡도는 정렬하는 데 걸리는 시간 O(N^2 log N^2)에 동적계획법을 수행하는 데 걸리는 시간 O(N^2)을 더해서 O(N^2 log N)이 됩니다.

baekjoon 9년 전 0

위의 방법으로 해도 되고, DFS를 이용해서 중복된 값을 계산하지 않게 Memoization을 사용할 수도 있습니다. 이 방법의 복잡도는 O(N^2)이 됩니다.

greentec 9년 전 0

음;; 그래프를 만들어서 갔던 길이 막혀 있는 곳이고, 그 길이 아니면 없애버리는 방법을 썼는데도 일단 계속 시간 초과가 나오네요..

아무래도 도와주시는 부분을 제가 잘 이해하지 못하는 것 같네요.

조금 더 고민해 보겠습니다.

#Memoization

def dfs(i,j):
    global count

    if i==n[0] and j==n[1]:
        count+=1
        return 1

    if data[i][j]==[0]:
        return 0

    way=0
    if 1 in data[i][j]:
        way+=1
        result=dfs(i-1,j)
        if result==0:
            data[i][j].remove(1)
            way-=1
    if 2 in data[i][j]:
        way+=1
        result=dfs(i,j+1)
        if result==0:
            data[i][j].remove(2)
            way-=1
    if 3 in data[i][j]:
        way+=1
        result=dfs(i+1,j)
        if result==0:
            data[i][j].remove(3)
            way-=1
    if 4 in data[i][j]:
        way+=1
        result=dfs(i,j-1)
        if result==0:
            data[i][j].remove(4)
            way-=1

    if way==0:
        data[i][j]=[0]
        return 0
    return 1
    
n=map(int, raw_input().split())
m=[]
m.append([99999]*(n[1]+2))
for i in range(1, n[0]+1):
    m.append(list())
    m[i].append(99999)
    m[i].extend(map(int, raw_input().split()))
    m[i].append(99999)
m.append([99999]*(n[1]+2))

#Make Graph
data=[]
temp=[[0]]*(n[1]+2)
data.append(temp)
for i in range(1, n[0]+1):
    data.append(list())
    data[i].append([0])
    for j in range(1, n[1]+1):
        temp=[0]
        if m[i-1][j]<m[i][j]:
            temp.append(1)
        if m[i][j+1]<m[i][j]:
            temp.append(2)
        if m[i+1][j]<m[i][j]:
            temp.append(3)
        if m[i][j-1]<m[i][j]:
            temp.append(4)
        data[i].append(temp)
    data[i].append([0])

temp=[[0]]*(n[1]+2)
data.append(temp)

count=0
dfs(1,1)

print count

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1520 테스트 케이스 요청

greentec 9년 전 0

baekjoon 9년 전 0

greentec 9년 전 0

baekjoon 9년 전 0

greentec 9년 전 0

greentec 9년 전 0

h0ngjun7 9년 전 0

baekjoon 9년 전 0

greentec 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말