가끔은 뇌에 과부화가

#16929번 Two Dots https://www.acmicpc.net/problem/16929

16929번: Two Dots

무난하게 풀 수 있을거라 생각했다.

 

N, M = map(int, input().split())
mat = []
attrs = set()

for i in range(N):
    tmp = []
    for j in input():
        attrs.add(j)
        tmp.append(j)
    mat.append(tmp)


def print_mat(mat):
    for i in mat:
        print(i)


def solve(target):
    # find first target position
    start = []
    for i in range(N):
        for j in range(M):
            if mat[i][j] == target:
                start = [i, j]
                break
        if len(start) > 0:
            break

    # dfs visit record
    visited = [[False]*M for _ in range(N)]
    # dfs direction
    dr = [1, 0, -1, 0]
    dc = [0, 1, 0, -1]

    def dfs(prev, depth, visited):
        if depth >= 4 and prev == start:
            print(target, True)
            return True

        for i in range(4):
            nr, nc = prev[0]+dr[i], prev[1]+dc[i]
            if 0 <= nr < N and 0 <= nc < M and not visited[nr][nc]:
                if mat[nr][nc] == target:
                    visited[nr][nc] = True
                    dfs([nr, nc], depth+1, visited)
                    visited[nr][nc] = False

    dfs(start, 1, visited)
    print_mat(visited)


solve("B")

근데 잘 안되길래 이게 뭔가 했더니

 

solve함수 내에서 제일 처음 나오는 target값만 가지고 진행한다.

모든 target값에서 탐색이 필요한데

이게 뭐하는...

 

왜 몰랐지??....

 

 

N, M = map(int, input().split())
mat = [[x for x in input()] for _ in range(N)]

# dfs visit record
visited = [[False]*M for _ in range(N)]
# dfs direction
dr = [1, 0, -1, 0]
dc = [0, 1, 0, -1]


def dfs(start, prev, depth, visited):
    # print(depth)
    # print_mat(visited)
    if depth >= 4 and prev == start:
        print("Yes")
        exit()

    for i in range(4):
        nr, nc = prev[0]+dr[i], prev[1]+dc[i]
        if 0 <= nr < N and 0 <= nc < M and not visited[nr][nc]:
            if mat[nr][nc] == mat[start[0]][start[1]]:
                visited[nr][nc] = True
                dfs(start, [nr, nc], depth+1, visited)
                visited[nr][nc] = False


for i in range(N):
    for j in range(M):
        dfs([i, j], [i, j], 0, visited)

print("No")

모든 위치를 탐색하게끔 바꿨다.

 

더 효율적으로 만들 수 있을 것 같다.

 

이제 골드 3~5정도는 무난하게 풀어가는 느낌이 든다! (플레로 가는 길인가..?)

 

근데 가끔은 머리가 터질 듯한 느낌이 들기도 한다. 

 

그래도 오늘 62일차 연속 스트릭을 찍었기에

만족스럽게 잠에 들 수 있을 것 같다.

 

 

https://solved.ac/profile/dlgustmd3590

solved.ac - dlgustmd3590

 

플래티넘 되고싶다!!

 

아니 앞으로 만날 코테 다 통과하고싶다!!

뿌셔버려!!