글 읽기 - 15%에서 자꾸 나갑니다... 도와주세요

crucialzint 1년 전 0

반례까지 다 찾아서 통과했다!

하고 돌리면 15%에서 죽네요.

하...왜 이럴까요

#백준 16954 움직이는 미로 탈출


wall=[]
room=[]

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

for x in range(8):
    data=list(input().rstrip())
    room.append(data)
    for y in range(8):
        if data[y]=='#':
            wall.append([x,y])

man=[]
man.append([7,0])


out=0
visited=[[False]*8 for _ in range(8)]
visited[7][0]=True
while man:
    new_man=[]
    away=0
    for i in range(len(man)):
        x,y=man[i]
        if x==0 and y==7:
            out=1
            away=1
            break
        on=0
        for d in range(8):
            nx=x+dx[d]
            ny=y+dy[d]

            if nx<0 or nx>=8 or ny<0 or ny>=8:
                continue

            if room[nx][ny]=='#' or [nx,ny] in wall:
                continue
            if visited[nx][ny]==True:
                continue

            new_man.append([nx,ny])
            visited[nx][ny]=True
            on+=1
        if on==0:
            new_man.append([x,y])
    if away==1:
        break
    man.clear()
    man=new_man
    man.sort()
    new_wall=[]
    while wall:
        wx,wy=wall.pop(0)
        nwx=wx+1
        if nwx>=8:
            room[wx][wy]='.'
            continue

        else:
            if [nwx,wy] in man:
                p=man.index([nwx,wy])
                man.pop(p)
            room[nwx][wy]='#'
            new_wall.append([nwx,wy])
            room[wx][wy]='.'
    wall=new_wall
    wall.sort()




print(out)

rlackstjq987 1년 전 1

" 인접한 한 칸 또는 대각선 방향으로 인접한 한 칸으로 이동하거나, 현재 위치에 서 있을 수 있다. 이동할 때는 빈 칸으로만 이동할 수 있다. "

dxdy 에서 현재 위치에 가만히 있는 경우가 빠진 듯 합니다.

crucialzint 1년 전 1

저는 가만히 있는 경우를 표현하기 위해,

on이라는 변수를 두고,

8방향 중 하나라도 움직이면 on+1했습니다.

만약, on이 0이라면 8방향 중 어디에도 못간 경우이므로

다시 원래 위치인 x,y를 넣어줬습니다.

혹시 이렇게 해도 가만히 있는 경우가 구현이 안되는건가요??

rlackstjq987 1년 전 1

우선 on 플래그를 통해서 가만히 있는 상태를 구현하려 하신 점은 보지 못했습니다. 다만, 가만히 있어야 할 때 문제가 생기는 것은 맞는 듯 합니다.

구현하신 코드는 만약 8방향 중 갈 곳이 없다면 가만히 서있게 되는 선택지를 부여하는 것인데,

반대로 8방향 중 갈 수 있는 방향이 하나라도 있다면 가만히 서있는다는 선택지는 주어지지 않게 됩니다.

crucialzint 1년 전 0

댓글 다시 읽어보니 어떤 의미인지 이해가 되었습니다.

즉, 모조건 가만히 있는 경우를 생각해야하는데, 처음 구현한 코드대로는 가만히 있는다는 게 구현이 안되었다는 의미였군요.

그래서 다시 고쳤습니다.

현재 x,y좌표의 visited를 False로 고친 다음에,

가만히 있는 걸 받는 걸로 코드를 수정해봤어요.

그런데 흠...

이 방법도 15%에서 걸리네요.

제가 뭔가를 놓친 거 같은데...아직은 잘 모르겠네요

#백준 16954 움직이는 미로 탈출


wall=[]
room=[]

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

for x in range(8):
    data=list(input().rstrip())
    room.append(data)
    for y in range(8):
        if data[y]=='#':
            wall.append([x,y])

man=[]
man.append([7,0])


out=0
visited=[[False]*8 for _ in range(8)]
visited[7][0]=True
while man:
    new_man=[]
    away=0
    for i in range(len(man)):
        x,y=man[i]
        if x==0 and y==7:
            out=1
            away=1
            break
        visited[x][y]=False
        for d in range(9):
            nx=x+dx[d]
            ny=y+dy[d]

            if nx<0 or nx>=8 or ny<0 or ny>=8:
                continue

            if room[nx][ny]=='#' or [nx,ny] in wall:
                continue
            if visited[nx][ny]==True:
                continue

            new_man.append([nx,ny])
            visited[nx][ny]=True

    if away==1:
        break
    man.clear()
    man=new_man
    man.sort()
    new_wall=[]
    while wall:
        wx,wy=wall.pop(0)
        nwx=wx+1
        if nwx>=8:
            room[wx][wy]='.'
            continue

        else:
            if [nwx,wy] in man:
                p=man.index([nwx,wy])
                man.pop(p)
            room[nwx][wy]='#'
            new_wall.append([nwx,wy])
            room[wx][wy]='.'
    wall=new_wall
    wall.sort()




print(out)

rlackstjq987 1년 전 1

line 55부터 구현하신 벽의 움직임 부분도 오류가 납니다.
nwx 에 이미 벽이 있는 상황. 즉, 벽이 연달아 있는 상황에서 벽이 중복되어 사라집니다.

Input )

........
........
........
........
#.......
#.......
.#......
.#......

위 입력을 가지고 1초 후 벽의 상태를 디버깅으로 확인해보세요

........
........
........
........
........
#.......
#.......
.#......
가 아닌 다른 상태가 만들어집니다.

crucialzint 1년 전 0

어떤 건지 인지해서 수정했는데....

하...또 15%에서 막히네요.

진짜 미치겠네요.

반례도 다 맞는데...

#백준 16954 움직이는 미로 탈출


wall=[]
room=[]

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

for x in range(8):
    data=list(input().rstrip())
    room.append(data)
man=[]
man.append([7,0])


out=0
visited=[[False]*8 for _ in range(8)]
visited[7][0]=True
while man:
    new_man=[]
    away=0
    for i in range(len(man)):
        x,y=man[i]
        if x==0 and y==7:
            out=1
            away=1
            break
        visited[x][y]=False
        for d in range(9):
            nx=x+dx[d]
            ny=y+dy[d]

            if nx<0 or nx>=8 or ny<0 or ny>=8:
                continue

            if room[nx][ny]=='#':
                continue
            if visited[nx][ny]==True:
                continue

            new_man.append([nx,ny])
            visited[nx][ny]=True

    if away==1:
        break
    man.clear()
    man=new_man
    man.sort()
    for x in range(7,-1,-1):
        for y in range(8):
            if room[x][y]=='#':
                if x==7:
                    room[x][y]='.'
                else:
                    room[x+1][y]='#'
                    room[x][y]='.'
                    if [x+1,y] in man:
                        p=man.index([x+1,y])
                        man.pop(p)



print(out)

rlackstjq987 1년 전 1

https://www.acmicpc.net/board/...

다른분이 올려주신 테스트케이스입니다.

한번 확인해보세요.

crucialzint 1년 전 0

결국 그냥 다른 방식으로 풀었네요.

아마 저 방식으로 벽을 움직이면

뭔가가 잘 안되는 것 같네요.

도와주셔서 감사합니다.

yssgood9708 1년 전 0

while wall:

wx,wy=wall.pop(0)

nwx=wx+1

if nwx>=8:

room[wx][wy]='.'

continue

else:

if [nwx,wy] in man:

p=man.index([nwx,wy])

man.pop(p)

room[nwx][wy]='#'

new_wall.append([nwx,wy])

room[wx][wy]='.'

wall=new_wall

wall.sort()

이미 푸셨겠지만 저도 15프로에서 막혔다가 저기 man.pop(p) 를 해준다음에 man 이 위치하고 있는 좌표에 visited 를 False 로 재설정 해주면 됐습니다!

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

문제

문제

출처

ICPC

15%에서 자꾸 나갑니다... 도와주세요

crucialzint 1년 전 0

rlackstjq987 1년 전 1

crucialzint 1년 전 1

rlackstjq987 1년 전 1

crucialzint 1년 전 0

rlackstjq987 1년 전 1

crucialzint 1년 전 0

rlackstjq987 1년 전 1

crucialzint 1년 전 0

yssgood9708 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말