코딩테스트(소프티어)_이미지 프로세싱_3단계

코딩테스트(소프티어)_이미지 프로세싱_3단계

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId;=627&sw;_prbl_sbms_sn=37518

처음에는 인접셀을 검사할 때 재귀함수를 이용했다(아래 코드에서 changeColor2)

예시를 실행시켰을 때는 문제가 없었는데, 제출을 하고 보니 몇 개 문항에서 런타임 에러가 떠서 왜 그런지 이리저리 찾아보다가 아래 2가지로 추정을 했다.

1. 이중배열에 없는 인덱스 참조(ex. -1, H, W 등)

2. 재귀함수 호출 횟수 과다

인덱스는 검사를 해도 문제가 없는 듯 해서, 재귀함수로 구현한 부분을 while문으로 stack으로 구현했더니 바로 통과를 한다

지난 번에도 유사한 문제에서 시간초과 + 런타임 에러가 나서 고생한 적이 있는데, 앞으로 이중 행렬에서 인접셀을 검사하는 방식에서는 Stack을 이용해서 구현해야겠다

풀이

changeColor 함수 최초에 입력받은 i,j 를 colorStack 배열에 넣어주고 visited 1을 해주고 시작.

-> 주의 colors[i-1][j-1] 로 인덱스를 맞춰줘야 함 colorStack의 길이가 0이 될 때까지 while 문 실행 colorStack에서 마지막 원소를 pop해주고 최초 칼라와 동일한지 비교해서, 동일하다면 인접 셀 4개를 colorStack에 push해준다. 이 때, colors 이중배열의 index를 벗어나거나, visited=1(이미 방문)이라면 안넣어주는 조건을 추가해준다. 다 끝나고나면 return colors

정답을 출력할 때는 Array.join(' ') 함수를 사용해서 한 줄 씩 출력해준다.

코드

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('

').map(e=>e.split(' ')) // console.log(input) const H = parseInt(input[0][0]) const W = parseInt(input[0][1]) const Colors = input.slice(1,1+H) const Q = parseInt(input[1+H][0]) const Calculates = input.slice(2+H) let NewColors = Colors.map(e=>e.slice()) for(let idx = 0;idxe.slice()),i,j,c,originC,0) //const visited = Array.from(Array(H), e=> Array(W).fill(0)) // NewColors = changeColor2(NewColors.map(e=>e.slice()),i,j,c,originC,visited) } for(let i=0;i Array(W).fill(0)) colorStack.push([i-1,j-1]) while(colorStack.length !==0){ const idx = colorStack.pop() visited[idx[0]][idx[1]] = 1 if(idx[0] < 0 || idx[1] <0 || idx[0] >=H || idx[1] >=W) continue if(parseInt(colors[idx[0]][idx[1]]) === originC){ colors[idx[0]][idx[1]] = c if((idx[0]-1) >= 0 && visited[idx[0]-1][idx[1]] === 0) colorStack.push([idx[0]-1,idx[1]]) if((idx[0]+1) <= H-1 && visited[idx[0]+1][idx[1]] === 0) colorStack.push([idx[0]+1,idx[1]]) if((idx[1]-1) >= 0 && visited[idx[0]][idx[1]-1] === 0) colorStack.push([idx[0],idx[1]-1]) if((idx[1]+1) <= W-1 && visited[idx[0]][idx[1]+1] === 0) colorStack.push([idx[0],idx[1]+1]) } } return colors } function changeColor2(colors,i,j,c,originC,visited){ visited[i-1][j-1] = 1 if(i-1 <0 || j-1 <0 || i-1 >=H || j-1>=W) return colors if(parseInt(colors[i-1][j-1]) === originC){ colors[i-1][j-1] = c if((i-1) > 0 && visited[i-2][j-1] === 0) colors = changeColor(colors,i-1,j,c,originC,visited) if((i+1) <= H && visited[i][j-1] === 0) colors = changeColor(colors,i+1,j,c,originC,visited) if((j-1) > 0 && visited[i-1][j-2] === 0) colors = changeColor(colors,i,j-1,c,originC,visited) if((j+1) <= W && visited[i-1][j] === 0) colors = changeColor(colors,i,j+1,c,originC,visited) } return colors }

참고사이트

런타임 에러가 난다면 아래 경우를 의심해 볼 것

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

from http://sbiografia.tistory.com/76 by ccl(A) rewrite - 2021-11-20 12:27:47