글 읽기 - (정답코드)

nayounsang1 1년 전 1

dfs를 호출할때 마다 code변수를 1을 더해주고 방문한 곳은 code의 값으로 바꿔서 방문처리를 해줬습니다.

예를들어 code가 5이고 특정 점에서 dfs를 해주면 탐색하는 점들은 값이 5로 바뀌고

만약 마지막점까지 탐색했을 때

1. 탐색이 끊긴 이유가 값이 5인 곳을 만나서

이 경우엔 새로운 사이클이므로 안전영역 1 추가

2.탐색이 끊긴 이유가 값이 5가 아닌 곳을 만나서

이 경우엔 다른 사이클로 진입 가능하므로 안전영역 추가 없음

n,m = map(int,input().split())
board = []
for i in range(n):
    board.append(list(input()))
########TEST########
n,m = 3,3
board = [
    'RDD','ULD','ULL'
]
board = list(map(list,board))
#expect 12
####################
dir = 'UDRL'
def go(x,y):#각 방향별 이동법
    v = board[y][x]
    nx,ny = x,y
    if v == 'U':
        ny -= 1
    elif v == 'D':
        ny += 1
    elif v == 'R':
        nx += 1
    else:
        nx -= 1
    return [nx,ny]
def dfs(x,y,code):
    stack = [(x,y)]
    last = [(x,y),(x,y)]#마지막 탐색좌표 저장위함
    while stack:
        px,py = stack.pop()
        nx,ny = go(px,py)
        board[py][px] = str(code)#방문처리(숫자를 문자열로 바꾼 것임)
        last = [(px,py),(nx,ny)]#마지막 탐색좌표 갱신
        if board[ny][nx] in dir:#방문안한 곳이라면 스택에 추가
            stack.append((nx,ny))
    fx,fy = last[0]
    sx,sy = last[1]
    if board[fy][fx] == board[sy][sx]:#만약 같은 사이클에 속해있으면
        return 1
    else:#만약 다른 사이클로 진입 가능하다면
        return 0
code = 0
cnt = 0
for y in range(n):
    for x in range(m):
        if board[y][x] in dir:
            cnt += dfs(x,y,code)
            code += 1
print(cnt)

dong5995 1년 전 2

반례입니다.

2 2
RL
RL

정답: 2
    
4 2
RD
UL
RD
UL

정답: 2

4 4
RDLL
ULLL
RDRD
ULUL

정답: 3

dong5995 1년 전 0

그리고 예제 입력도 틀리네요.

nayounsang1 1년 전 0

직접 돌려봤는데 예제랑 반례 다 맞게 나옵니다..

dong5995 1년 전 0

그대로 복붙해서 돌렸는데 전부 1로 나와요.

혹시 코드 다시 복사해서 올려주실 수 있을까요

dong5995 1년 전 0

아 테스트 코드 때문에 그렇네요;;

dong5995 1년 전 0

테스트 코드 지우니까 AC 뜨는데요??

nayounsang1 1년 전 0

아 복붙을 수정하기전 이상한 코드?로 했네요.. 죄송합니다ㅎㅎ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

(정답코드)

nayounsang1 1년 전 1

dong5995 1년 전 2

dong5995 1년 전 0

nayounsang1 1년 전 0

dong5995 1년 전 0

dong5995 1년 전 0

dong5995 1년 전 0

nayounsang1 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말