정올 1108(BFS), acmicpc 1987(DFS,c++)

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=388&sca=3070

파이썬이라 그런지 알고리즘이 문젠지 처음에는 시간초과가 나왔었다. 시간초과임에도 60점을 

주는거보니 답은 맞았다 싶어서 시간초과를 없애는데 주력했다.

처음에는 그냥 말그대로 반복문을 다 돌면서 '하나하나' BFS로 거리를 구했는데 시간초과가 떴다.

곰곰히 생각하다가 BFS안에서 답이 나올때마다 저장해주자는 식으로 코드를 작성했고, 

BFS가 끝난 후 반복문을 다시 돌때 이미 답이 있으면 그냥 무시하고 도는 식으로 코드를 짰다. 

시간이 3800ms정도 걸리던게 940정도로 확 줄면서 통과했다.

# -*- encoding: cp949 -*-
import Queue
answer = [[0 for j in xrange(501)] for i in xrange(501)]
def bfs(graph,v,arr,visted):
    global num
    global answer
    q = Queue.Queue()
    q.put(v)
    while not q.empty():
        for k in xrange(q.qsize()):
            p = q.get()
            if v!=p and answer[v][p]==0 and p in xrange(1,max+1): #이거때문에 시간초과가 없어졌다.
                answer[v][p] = num
            if visited[p]==0:
                visited[p] = 1
            for i in xrange(len(graph)):
                if graph[p][i] == 1 and visited[i]==0:
                    q.put(i)
        num += 1

n = int(raw_input())
graph = [[0 for j in xrange(501)] for i in xrange(501)]
max = 0
for i in xrange(n):
    x,y = map(int,raw_input().split())
    max = x if x > max else y if y > max else max
    graph[x][y] = 1

for i in xrange(1,max+1):
    for j in xrange(1,max+1):
        if i!=j:
            num = 0
            visited = [0 for k in xrange(501)]
            if answer[i][j]==0:
                bfs(graph,i,j,visited)

print round(sum(map(lambda x:sum(x),answer))/float(max*(max-1)),3)

https://www.acmicpc.net/problem/1987

분명히 알고리즘은 맞는거같은데 파이썬이라 그런지 모르겠는데 시간초과가 떠버린다. 

추가. c++로 짰더니 제대로 동작한다.

# -*- encoding: cp949 -*-
answer = 0
def back_tracking(maps, p, move):
    global answer
    for i in range(4):
        y,x = p[0]+[1,0,-1,0][i],p[1]+[0,-1,0,1][i]
        if y>n-1 or x>m-1 or x<0 or y<0:
            continue
        if visited[ord(maps[y][x])-65]==0:
            #print move,maps[y][x],visited
            visited[ord(maps[y][x])-65] = 1
            back_tracking(maps,[y,x],move+1)
            visited[ord(maps[y][x])-65] = 0
    if move > answer:
        answer = move
    
n,m = map(int,raw_input().split())
maps = [list(raw_input()) for i in range(n)]
visited = [0 for i in range(26)]
visited[ord(maps[0][0])-65] = 1
back_tracking(maps, [0,0], 1)
print answer

# -*- encoding: cp949 -*-
answer = []
def dfs(maps, p):
    global answer
    visited = [0 for i in xrange(26)]
    visited[ord(maps[0][0])-65] = 1
    stack = []
    stack.append([p,visited,1])
    while stack!=[]:
        p = stack.pop()
        answer.append(p[2])
        for i in xrange(4):
            y,x = p[0][0]+[1,0,-1,0][i],p[0][1]+[0,-1,0,1][i]
            if y>n-1 or x>m-1 or x<0 or y<0 or p[1][ord(maps[y][x])-65]!=0:
                continue
            p[1][ord(maps[y][x])-65] = 1
            stack.append([[y,x],p[1][:],p[2]+1])
            p[1][ord(maps[y][x])-65] = 0
     
n,m = map(int,raw_input().split())
maps = [list(raw_input()) for i in xrange(n)]

s = time.time()
dfs(maps, [0,0])
print max(answer)

#include <iostream>
using namespace std;

int n,m;
int yi[] = {1,0,-1,0};
int xi[] = {0,-1,0,1};
int visited[26] = {0,};
int answer = 0;

void dfs(char map[][21],int py,int px,int move)
{
	for(int i=0;i<4;i++)
	{
		int y = py + yi[i];
		int x = px + xi[i];
		if(y>n-1 || x>m-1 || x<0 || y<0 || visited[map[y][x]-65]!=0)
			continue;
		visited[map[y][x]-65] = 1;
		dfs(map,y,x,move+1);
		visited[map[y][x]-65] = 0;
	}
	if(move > answer)
		answer = move;
}

int main()
{
	cin>>n>>m;
	char map[21][21];
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			cin>>map[i][j];
	visited[map[0][0]-65] = 1;
	dfs(map,0,0,1);
	cout<<answer<<endl;
    return 0;
}