🥇[백준] 1987 알파벳 (골드4) / DFS, list, set, dict 시간복잡도 정리

문제요약

나의 코드 및 설명 01 (틀렸습니다)

• 처음으로 제출한 코드. 예제 출력값이 맞게 나온다고 그냥 제출했다가 틀렸다는 판정 받았다. 지금 보니 하위 dfs 함수 호출 전에 방문 체크를 해두고, 다시 돌아와서는 방문 체크 해제를 안했다. 또한, count 값이 계속 더해지는 것도 이상하다.

def dfs(x,y):
    global count
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx<0 or ny<0 or nx>=c or ny>=r:
            continue
        else:
            if alphabet_list[ny][nx] not in v:
                v.append(alphabet_list[ny][nx])
                count += 1
                dfs(nx,ny)

r, c = map(int, input().split()) # 세로, 가로

alphabet_list = [list(input()) for _ in range(r)]

dx = [0,1,0,-1]
dy = [-1,0,1,0]


count = 1

v = [alphabet_list[0][0]]
dfs(0,0)

print(count)

나의 코드 및 설명 02 (시간초과)

• 다시 작성한 코드. 솔직히 맞을 줄 알았는데 시간초과가 떴다. dfs함수가 호출될 때 마다 함수 파라미터 count 값과, 전역변수로 선언된 ans 중 큰 값을 ans에 저장한다. 이로써 앞서 작성한 코드에서 count+=1 해주는 것을 대체할 수 있게 되었다. 또한, 하위 dfs 함수를 수행하고 나서 방문체크 해제 처리를 해주었다.

def dfs(x,y,count):
    global ans
    ans = max(ans, count)
    for i in range(4): #네 방향에 대하여
        #가능한 다음 좌표를 만들고
        nx = x + dx[i]
        ny = y + dy[i]
        if nx<0 or ny<0 or nx>=c or ny>=r: #범위를 벗어나면 안됨
            continue
        else: #범위 안에서
            if alphabet_list[ny][nx] not in v: #다음좌표의 알파벳이 방문테이블에 없다면
                v.append(alphabet_list[ny][nx]) #방문테이블에 추가
                dfs(nx,ny,count+1) #count를 1씩 더하며, 다음 좌표에 대한 dfs호출
                v.pop() #돌아와서는 방문체크 해제

r, c = map(int, input().split()) # 세로, 가로

alphabet_list = [list(input()) for _ in range(r)]

dx = [0,1,0,-1]
dy = [-1,0,1,0]

ans = 0
v = [alphabet_list[0][0]] #처음 알파벳 방문처리
dfs(0,0,1)

print(ans)

나의 코드 및 설명 03 (맞았습니다)

• 리스트 대신 set()을 활용하여 시간을 단축하였다. 시간복잡도는 아래에 정리해두었다. 리스트의 경우, if~ in 을 활용하여 조건을 탐색할 때 시간복잡도는 O(n)이다. 하지만 set()을 활용하면 O(1)로 단축할 수 있다.

def dfs(x,y,count):
    global ans
    ans = max(ans, count)
    for i in range(4): #네 방향에 대하여
        #가능한 다음 좌표를 만들고
        nx = x + dx[i]
        ny = y + dy[i]
        if nx<0 or ny<0 or nx>=c or ny>=r: #범위를 벗어나면 안됨
            continue
        else: #범위 안에서
            if alphabet_list[ny][nx] not in v: #다음좌표의 알파벳이 방문테이블에 없다면
                v.add(alphabet_list[ny][nx]) #방문테이블에 추가
                dfs(nx,ny,count+1) #count를 1씩 더하며, 다음 좌표에 대한 dfs호출
                v.remove(alphabet_list[ny][nx]) #돌아와서는 방문체크 해제

r, c = map(int, input().split()) # 세로, 가로

alphabet_list = [list(input()) for _ in range(r)]

dx = [0,1,0,-1]
dy = [-1,0,1,0]

ans = 0
v = set() 
v.add(alphabet_list[0][0])#처음 알파벳 방문처리
dfs(0,0,1)

print(ans)

list 시간복잡도

set 시간복잡도 

dict 시간복잡도

피드백

시간복잡도를 고려하지 못했다면 못풀었을 것 같다. 이번 기회로 방문테이블을 만들어야할 시에 리스트 말고 set()을 활용할 수 있다는 것을 배웠다. 틈틈이 시간복잡도가 궁금할 때 들어와서 확인하면서 숙지해야겠다.