백준 18428: 완전탐색, dfs bfs, 백트래킹 이 아닌 풀이 방법으로 pypy3 정답 코드들 중 실행시간 기준 전체 6등!

사실 이게 dbfs 문제라고 했을 떄 감을 못잡았었다... 그냥 어렴풋한 감만 있는 느낌이었고, 애초에 그렇게 푸는게 왠지 비효율적일 것 같다고 생각이 들어서 이 풀이를 고안했다.

정석적인 풀이는 가능한 모든 빈공간 3개를 조합으로 뽑아서, 거기에 블록 놔보고 이게 정답 처리가 될수있는지 아닌지를 따져서 푸는 문제다. 저번에 푼 그 뱀 문제였나? 그거랑 매우 유사하다. 풀이 보니까 다들 그렇게 풀었고 나처럼 푼 사람은 나밖에 없었다!!!

 

 

ㅇ

454개 pypy3 코드 중

 

import sys
from collections import deque, defaultdict, Counter

input = sys.stdin.readline
N = int(input())
mapShape, teachers, obstacles, obstacles_cnt = deque([]), deque([]), defaultdict(set), deque([])
answer = True
for x in range(N):
    mapShape.append(list(map(str, input().split())))
    for y in range(N):
        if mapShape[x][y] == "T":
            teachers.append((x, y))


for x, y in teachers:
    for up in range(x - 1, -1, -1):
        if mapShape[up][y] == "S":
            if up != x - 1:
                for x_ in range(up+1, x):
                    obstacles[((x, y), "up")].add((x_, y))
                    obstacles_cnt.append((x_, y))
            else:
                answer = False
            break
    if not answer:
        print("NO")
        break

    for down in range(x + 1, N):
        if mapShape[down][y] == "S":
            if down != x + 1:
                for x_ in range(x+1, down):
                    obstacles[((x, y), "down")].add((x_, y))
                    obstacles_cnt.append((x_, y))
            else:
                answer = False
            break
    if not answer:
        print("NO")
        break

    for left in range(y - 1, -1, -1):
        if mapShape[x][left] == "S":
            if left != y - 1:
                for y_ in range(left+1, y):
                    obstacles[((x, y), "left")].add((x, y_))
                    obstacles_cnt.append((x, y_))
            else:
                answer = False
            break
    if not answer:
        print("NO")
        break

    for right in range(y + 1, N):
        if mapShape[x][right] == "S":
            if right != y + 1:
                for y_ in range(y + 1, right):
                    obstacles[((x, y), "right")].add((x, y_))
                    obstacles_cnt.append((x, y_))
            else:
                answer = False
            break
    if not answer:
        print("NO")
        break

if answer:
    obstacles_cnt = Counter(obstacles_cnt)
    obstacles_cnt = set(filter(lambda k: obstacles_cnt[k] >= 2, obstacles_cnt.keys()))
    cnt = len(obstacles_cnt)
    for v in obstacles.values():
        if not v.intersection(obstacles_cnt):
            cnt += 1

    if cnt <= 3:
        print("YES")
    else:
        print("NO")