acmicpc.net 4963(백트래킹), 1759(BFS?;;)

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

쉬운 백트래킹 문제. bfs나 dfs로도 풀수 있을듯

# -*- encoding: cp949 -*-
import sys
sys.setrecursionlimit(100000)
answer = ''

def backtracking(y,x):
    global land_count
    global maps
    maps[y][x] = land_count
    for i in xrange(8):
        ty,tx = y+[1,0,-1,0,-1,-1,1,1][i],x+[0,-1,0,1,-1,1,-1,1][i]
        if ty > h-1 or tx > w-1 or ty < 0 or tx < 0 or maps[ty][tx]!=1:
            continue
        backtracking(ty,tx)

while True:
    land_count = 0
    w,h = map(int,raw_input().split())
    if w==0 and h==0:
        break
    maps = [map(int,raw_input().split()) for i in xrange(h)]
    for i in xrange(h):
        for j in xrange(w):
            if maps[i][j]==1:
                land_count -= 1
                backtracking(i,j)
    answer+=str(-land_count)+'\n'
print answer

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

솔직히 큐를 쓰긴 했는데..... 로직을 자세히 살펴보면 DFS같다....... 맘에 안드는 코드....

코드를 짜다 아 이렇게하면되겠다! 싶어서 바꾼게 너무 많다. 문제는 풀었는데 기분이 그렇게 좋지는....

# -*- encoding: cp949 -*-
import Queue
def bfs(index, v, c):
    global alpha
    visited = [0 for i in xrange(26)] #중복 방지용 리스트
    q = Queue.Queue()
    visited[ord(alpha[index])-97] = 1 #들어온 것의 중복방지를 해둔다.
    if alpha[index] in ['a','e','i','o','u']: #v는 모음, c는 자음을 뜻한다.
        q.put([alpha[index],v+1,c,visited,index])
    else:
        q.put([alpha[index],v,c+1,visited,index])
    
    while not q.empty():
        p = q.get()
        if len(p[0])==L: #길이가 L이 될경우 최소 모음 1개, 자음 2개인지 검사해서 맞으면 출력한다.
            v=c=0
            for i in xrange(len(p[0])):
                if p[0][i] in ['a','e','i','o','u']:
                    v += 1
                else: c += 1
            if v>=1 and c>=2:
                print p[0]
        for i in xrange(len(alpha)): #다 돌아가면서
            if i>p[4] and p[1] < L-len(p[0]) and p[3][ord(alpha[i])-97]==0 and alpha[i] in ['a','e','i','o','u']:
               #뒤에있는 글자이면서, 모음이 들어갈 자리가 있는지 확인하면서, 이미 쓴 글자인지, 모음인지 확인 후
                p[3][ord(alpha[i])-97] = 1 #방문했다고 체크하고
                q.put([p[0]+alpha[i],p[1]+1,p[2],p[3][:],i]) #해당 값들을 넣어준다. 순서대로 만들어진글자,모음+1,자음,중복체크할리스트,인덱스
                p[3][ord(alpha[i])-97] = 0
            elif i>p[4] and p[3][ord(alpha[i])-97]==0: #자음체크.
                p[3][ord(alpha[i])-97] = 1
                q.put([p[0]+alpha[i],p[1],p[2]+1,p[3][:],i])
                p[3][ord(alpha[i])-97] = 0

L,C = map(int,raw_input().split())
alpha = sorted(raw_input().split())
for i in xrange(len(alpha)):
    bfs(i,0,0)