[백준 1400번] 화물차(파이썬)

https://www.acmicpc.net/problem/1400

1400번: 화물차

이 문제는 억울함이 많았던...ㅠ

 

우선 처음에 생각했던 풀이는

'교차로를 만날 때

바로 신호등이 켜지는 경우와

신호가 켜지기 기다렸다가 건너는 케이스

두 가지를 구현한다'

였습니다.

 

#백준 1400번 화물차
from heapq import heappop,heappush
dx=[0,1,0,-1]
dy=[1,0,-1,0]

while True:
    m,n=map(int,input().split())
    if m==0 and n==0:
        break
    room=[[0]*n for _ in range(m)]
    tmp=[input().rstrip() for _ in range(m)]
    visited=[[1e9]*n for _ in range(m)]
    sx,sy=0,0
    ex,ey=0,0
    answer=1e9
    color=0
    coloring=[]
    for x in range(m):
        for y in range(n):
            if tmp[x][y]=='.':
                room[x][y]=-1
            elif tmp[x][y]=='#':
                room[x][y]=10
            elif tmp[x][y]=='A':
                sx,sy=x,y
                room[x][y]=10
            elif tmp[x][y] == 'B':
                ex,ey=x,y
                room[x][y]=10
            else:
                room[x][y]=int(tmp[x][y])
                color+=1
    if color:
        for _ in range(color):
            lo=input().split()
            if lo[1]=='-':
                start=0
                coloring.append([int(lo[0]), start, int(lo[2]), int(lo[2])+int(lo[3]),int(lo[2])+int(lo[3])+1])
            else:
                start=1
                coloring.append([int(lo[0]), start, int(lo[3]), int(lo[2])+int(lo[3]),int(lo[2])+int(lo[3])+1])
    #print(coloring)
    q=[]
    heappush(q,[0,sx,sy])
    visited[sx][sy]=0
    while q:
        cnt,x,y=heappop(q)
        if x==ex and y==ey:

            answer=min(answer,cnt)
            continue

        for d in range(4):
            nx=x+dx[d]
            ny=y+dy[d]

            if nx<0 or nx>=m or ny<0 or ny>=n:
                continue
            if room[nx][ny]==-1:
                continue


            if room[nx][ny]==10 and visited[nx][ny]>cnt+1:
                visited[nx][ny]=cnt+1
                heappush(q,[cnt+1,nx,ny])

            elif room[nx][ny]>=0 and room[nx][ny]<10:

                now_coloring=coloring[room[nx][ny]]
                now_time=cnt+1
                color_state=now_coloring[1]
                color_time=now_time%now_coloring[4]
                po=0

                #현재 신호등의 상태를 봐야함
                if color_time>now_coloring[2]:
                    po=1
                    color_state=(color_state+1)%2
                #방향이 같을 경우에는 그냥 통과하면 되는데
                #방향이 다르면 대기하다가 건너는 케이스도 존재함.
                #print(x,y,room[nx][ny],color_state,color_time,d,cnt)
                #방향이 같은 케이스
                if d%2==color_state:
                    if visited[nx][ny]>cnt+1:
                        visited[nx][ny]=cnt+1
                        #print(color_state,'right')
                        heappush(q,[cnt+1,nx,ny])
                #방향이 다르면 대기했다가 건너기
                else:
                    if po==0:
                        move_t=now_coloring[2]+1-color_time
                        go=cnt+move_t
                        if visited[nx][ny]>go:
                            visited[nx][ny]=go

                            heappush(q,[go,nx,ny])

                    else:
                        move_t=now_coloring[3]+1-color_time
                        go=cnt+move_t
                        if visited[nx][ny] > go:

                            visited[nx][ny] = go
                            heappush(q, [go, nx, ny])

    #print(visited)
    if answer==1e9:
        print('impossible')
    else:
        print(answer)
    p=input()

 

현재 이동하는 점에 대해서만 봐야지

시간초과가 안 뜰 것이라고 생각이 들었습니다만..

이 풀이는 33%에서 오답이 표시가 되었습니다.

왜 그럴까...고민고민을 하다가

이런 오류를 발견했습니다.

이게 0일때는 계산을 안하는 거니깐

참 어떻게해도 겁나 꼬였습니다.

그래서 구글링을 하다가

어떻거보면 원초적인 방법인

'신호등을 수동으로 켜주기'로 바꿨습니다.

 

#백준 1400번 화물차
from collections import deque
dx=[0,1,0,-1]
dy=[1,0,-1,0]

while True:
    m,n=map(int,input().split())
    if m==0 and n==0:
        break
    room=[[0]*n for _ in range(m)]
    tmp=[input().rstrip() for _ in range(m)]
    visited=[[False]*n for _ in range(m)]
    sx,sy=0,0
    ex,ey=0,0
    answer=1e9
    color=0
    coloring=[]
    for x in range(m):
        for y in range(n):
            if tmp[x][y]=='.':
                room[x][y]=-1
            elif tmp[x][y]=='#':
                room[x][y]=10
            elif tmp[x][y]=='A':
                sx,sy=x,y
                room[x][y]=10
            elif tmp[x][y] == 'B':
                ex,ey=x,y
                room[x][y]=10
            else:
                room[x][y]=int(tmp[x][y])
                color+=1
    if color:
        for _ in range(color):
            lo=input().split()
            if lo[1]=='-':
                start=0
                coloring.append([int(lo[0]), start, int(lo[2]), int(lo[2])+int(lo[3]),int(lo[2])+int(lo[3])])
            else:
                start=1
                coloring.append([int(lo[0]), start, int(lo[3])+int(lo[2]), int(lo[3]),int(lo[2])+int(lo[3])] )
    #print(coloring)
    q=deque()
    q.append([sx,sy])
    visited[sx][sy]=True
    time=0
    while q:
        size=len(q)
        time+=1

        while size:
            x,y=q.popleft()


            for d in range(4):
                nx=x+dx[d]
                ny=y+dy[d]

                if nx<0 or nx>=m or ny<0 or ny>=n:
                    continue
                if room[nx][ny]==-1:
                    continue


                if room[nx][ny]==10 and visited[nx][ny]==False:
                    visited[nx][ny]=True
                    q.append([nx,ny])
                    if nx==ex and ny==ey:
                        answer=time
                        break

                elif room[nx][ny]>=0 and room[nx][ny]<10:
                    now_color=coloring[room[nx][ny]]
                    color_state=now_color[1]
                    if d%2==color_state:
                        if visited[nx][ny]==False:
                            visited[nx][ny]=True
                            #print(color_state,'right')
                            q.append([nx,ny])
                    #방향이 다르면 대기했다가 건너기
                    else:
                        q.append([x,y])

            size-=1

        #신호등 하나하나 돌려주기
        for num in range(color):
            now_coloring=coloring[num]
            now_state=now_coloring[1]
            if now_state==0:
                if time>=now_coloring[2]:
                    coloring[num][1]=1
                    coloring[num][2]+=coloring[num][4]
            else:
                if time>=now_coloring[3]:
                    coloring[num][1]=0
                    coloring[num][3]+=coloring[num][4]


    if answer==1e9:
        print('impossible')
    else:
        print(answer)
    p=input()

 

근데 이대로 제출하니

메모리초과가 뜨는 거 있죠.

예시코드보고 조금씩 수정하다가

계속 메모리 초과가 떠서 열이 오르더군요.

#백준 1400번 화물차
from collections import deque
dx=[0,0,1,-1]
dy=[1,-1,0,0]

while True:
    m,n=map(int,input().split())
    if m==0 and n==0:
        break
    room=[]

    visited=[[False]*n for _ in range(m)]
    sx,sy=0,0
    ex,ey=0,0
    answer=1e9
    color=0
    coloring=[False for _ in range(10)]
    for x in range(m):
        tmp=input().rstrip()
        for y in range(n):
            if tmp[y]=='A':
                sx,sy=x,y
            elif tmp[y]=='B':
                ex,ey=x,y
            elif "0"<=tmp[y]<="9":
                color+=1
        room.append(tmp)
    for _ in range(color):
        lo=input().split()
        if lo[1]=='-':
            coloring[int(lo[0])]={'dir':lo[1] ,'a':int(lo[2]),'b':int(lo[3])+int(lo[2]),'sum':int(lo[3])+int(lo[2])}
        else:
            coloring[int(lo[0])]={'dir':lo[1],'a':int(lo[2])+int(lo[3]),'b':int(lo[3]),'sum':int(lo[3])+int(lo[2])}

    q=deque()
    q.append([sx,sy])
    visited[sx][sy]=True
    time=0
    out=False
    while q:
        size=len(q)
        time+=1
        while size:
            x,y=q.popleft()


            for d in range(4):
                nx=x+dx[d]
                ny=y+dy[d]

                if nx<0 or nx>=m or ny<0 or ny>=n:
                    continue
                if visited[nx][ny]==True:
                    continue
                if room[nx][ny]=='.':
                    continue


                if room[nx][ny]=='#':
                    visited[nx][ny]=True
                    q.append([nx,ny])

                elif "0"<=room[nx][ny]<="9":
                    num=int(room[nx][ny])

                    if d<2:
                        if coloring[num]['dir']=='-':
                            visited[nx][ny]=True
                            q.append([nx,ny])
                    #방향이 다르면 대기했다가 건너기
                        else:
                            q.append([x,y])
                    else:
                        if coloring[num]['dir'] == '|':
                            visited[nx][ny] = True
                            q.append([nx, ny])
                        # 방향이 다르면 대기했다가 건너기
                        else:
                            q.append([x, y])
                else:
                    answer=time
                    out=True
                    break
            size-=1
        if out==True:
            break
        #신호등 하나하나 돌려주기
        for num in range(color):

            now_state=coloring[num]['dir']

            if now_state=='-':
                if time>=coloring[num]['a']:
                    coloring[num]['a']+=coloring[num]['sum']
                    coloring[num]['dir']='|'
            else:
                if time>=coloring[num]['b']:
                    coloring[num]['b']+=coloring[num]['sum']
                    coloring[num]['dir']='-'



    if answer==1e9:
        print("impossible")
    else:
        print(answer)
    p=input()

결국 지도와 방향키를 숫자로 넣는대신에

직접 문자로 다 받는 경우로 다시 짜야지

메모리 초과에서 빠져나가더군요.

생각해보니

문자형은 메모리가 1byte고

숫자형은 최소 4byte이니

메모리 초과가 뜨는 게 당연할 수 도 있겠다...

싶긴한데.

이게 테스트 케이스가 20개 이하로

20개 전부 다 한다고 생각하면

저렇게 문자형으로 넣는 게

메모리초과가 안뜨는 방식이겠다는 생각도 드네요.

https://ji-hyeong.tistory.com/13

[백준-1400] 화물차 (Python)